Harte Lücken bei Problemen mit der maximalen Beschränkungszufriedenheit?

12

Eine äquivalente Formulierung des PCP-Theorems lautet: Für Max 3-SAT ist es -schwer, zwischen erfüllbaren Formeln und Formeln zu unterscheiden, bei denen höchstens r- Bruch der Klauseln erfüllbar sind (für einige r < 1 ).NPrr<1

Gibt es ein bekanntes Dichotomie-Theorem, das alle Max CSPs danach klassifiziert, ob sie harte Lücken aufweisen oder nicht?

Edit 16. Dezember 2010 : MAX CSP mit harter Lücke bedeutet, dass das Problem einen optimalen Unanpassungsfaktor hat. Zum Beispiel hat 3SAT harten Spalt an einer Stelle , da es Polynomzeit approximierbar auf einen Faktor , aber es ist N P Faktor -hard zu erhalten Näherung selbst wenn alle Klauseln sind erfüllbar.7/8NP7/8+ϵ

cc.complexity-theory pcp csp Mohammad Al-Turkistany
quelle

Antworten:

18

Prasad Raghavendra in der besten Veröffentlichung von STOC'08 hat eine Dichotomie-Vermutung für die Annäherung von Max-CSP unter der Annahme der Unique Games Conjecture bewiesen. So präsentierte er es ursprünglich nicht, aber er hielt einige Jahre später Vorträge, in denen er die Dinge auf diese Weise präsentierte, z. B. beim IAS, wo es auf Video aufgezeichnet wurde: http://www.math.ias.edu/seminars/abstract Ereignis = 36669

Der Unterschied zur SNP-Härte besteht darin, dass hier von quantitativ optimalen Ergebnissen gesprochen wird.

Dana Moshkovitz
quelle
3
Was bedeutet "quantitativ optimal"?
Suresh Venkat
3
Härtefaktor
6

Satz 5.14 von Khanna, Sudan, Trevisan und Williamson [KSTW01] liefert einen Dichotomiesatz für die Lückenversionen mit perfekter Vollständigkeit für die booleschen MaxCSP-Probleme.

[KSTW01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan und David P. Williamson. Die Approximierbarkeit von konstanten Zufriedenheitsproblemen. SIAM Journal on Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Tsuyoshi Ito
quelle
Interessantes Papier. In welcher Beziehung steht dieser Dichotomiesatz zu Raghavendras Ergebnis in Danas Antwort?
Mohammad Al-Turkistany
Ich denke, dass die Ergebnisse ziemlich unterschiedlich sind. Der Satz in [KSTW01], den ich in dieser Antwort erwähnte, handelt von der perfekten Vollständigkeitsversion, während das Ergebnis von Raghavendra dies nicht ist. Der Satz in [KSTW01] handelt von booleschem CSP, während es bei Raghavendra um CSP über jede Domäne geht. Aber Sie sollten es selbst überprüfen, da ich die Zeitung von Raghavendra nicht gut kenne.
Tsuyoshi Ito