Näherungshärte ohne den PCP-Satz

36

Eine wichtige Anwendung des PCP-Theorems ist, dass es Ergebnisse vom Typ "Härte der Approximation" liefert. In relativ einfacheren Fällen kann man eine solche Härte ohne PCP nachweisen. Gibt es jedoch einen Fall, in dem die Härte des Approximationsergebnisses zuerst mit dem PCP-Theorem bewiesen wurde, dh das Ergebnis war vorher nicht bekannt, aber später wurde ein direkterer Beweis gefunden, der nicht von PCP abhängt? Mit anderen Worten, gab es einen Fall, in dem PCP zuerst notwendig erschien, später jedoch beseitigt werden konnte?

cc.complexity-theory approximation-hardness pcp Andras Farago
quelle

Antworten:

35

Ein Beispiel ist dieses Papier:

Guruswami, V. & Khanna, S. (2004). Über die Härte von 4-Farben kann ein 3-Farben-Diagramm erstellt werden. SIAM Journal on Discrete Mathematics , 18 (1): 30-40. Verknüpfung

Khanna, Linial und Safra (2000) haben mit dem PCP-Theorem bewiesen, dass es NP-schwer ist, einen dreifarbigen Graphen mit nur vier Farben zu färben. Später gaben Guruswami & Khanna (2004) unter anderem einen PCP-freien Beweis für das gleiche Ergebnis.

vb le
quelle
11
Wären Sie bereit, den Artikel in Ihrer Antwort zu beschreiben, anstatt nur mit einem Hyperlink darauf zu verweisen?
Niel de Beaudrap
15

Für das Problem der maximalen Kantendisjunktionspfade in gerichteten Graphen basierte die Arbeit von Ma & Wang (2000) auf dem Etikettendeckelproblem, das wiederum auf dem PCP-Theorem basiert. Anschließend wurde von Guruswami et al. Eine einfache Reduktion über die Härte des 2-Disjointpath-Problems gefunden . al. (2003) was ebenfalls eine verbesserte Härte ergab.

Chandra Chekuri
quelle
Aber erfordert die 2-Disjointpath-Härte das PCP?
Suresh Venkat
3
(s1,t1)(s2,t2) in einem gerichteten Graphen G. Es wurde von Fortune, Hopcroft und Wylie gezeigt, dass es durch eine komplizierte Gadget-Reduktion von SAT NP-vollständig ist.
Chandra Chekuri
13

Es gibt Beispiele aus der Näherungszählung. Die ungefähre Zählung der Anzahl zufriedenstellender Zuordnungen einer NP-Beziehung kann nur schwieriger sein, als zu entscheiden, ob eine zufriedenstellende Zuordnung vorliegt. Es ist daher nicht verwunderlich, dass das PCP-Theorem nicht erforderlich ist, um die Härte für solche Probleme zu beweisen. Das PCP-Theorem bietet jedoch manchmal einen geeigneten Ausgangspunkt, z. B. für dieses Dokument, in dem die Anzahl unabhängiger Mengen in einem übersichtlichen Diagramm ungefähr gezählt wird: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Später erwies sich Sly als Härteergebnis für die Zählung unabhängiger Sätze, die nur auf der Standard-NP-Härte von Max-Cut basierten: http://arxiv.org/pdf/1005.5584v1.pdf

Dana Moshkovitz
quelle
1
Interessant - verbessert der UGC hier Slys Härte des Approximationsfaktors? (Edit: Ich denke nicht; er behauptetd=6ist optimal. Edit2: Könntest du etwas Stärkeres als PTASs ausschließen? Irgendeine Idee, ob die Unangemessenheit von MAX-CUT irgendetwas für eine Partition impliziert?)
Daniel Apon
2
@DanielApon: Ein späteres Ergebnis, das die Unangemessenheit von MAX-CUT verwendet, um ein noch stärkeres Unangemessenheitsergebnis zu erzielen: arxiv.org/abs/1203.2602 zeigt dies für einigec Es ist schwer, unabhängige Mengen in 6-regulären Graphen auf das Verhältnis genau zu zählen ecn. Ich denke nicht den optimalen Wert voncwurde untersucht, unter UGC oder auf andere Weise.
Colin McQuillan
10

Eine andere Antwort, die in einem etwas anderen Sinne als die vorherigen Antworten ist, ist diese Abhandlung von Uri Feige: Beziehungen zwischen durchschnittlicher Fallkomplexität und Approximationskomplexität .

Uri zeigt, dass durchschnittliche Fallannahmen das PCP-Theorem ersetzen können, um die Härte der Approximation einiger Probleme zu beweisen. Beachten Sie jedoch, dass wir nicht wissen, wie die Annahmen für den Durchschnittsfall zu beweisen sind, und wir haben einige Beweise dafür, dass wir sie auf der Grundlage von Standard-NP-Härte-Annahmen nicht beweisen können (siehe die Arbeiten von Feigenbaum-Fortnow, Bogdanov-Trevisan usw.).

Dana Moshkovitz
quelle