Ist Gap-3SAT NP-complete auch für 3CNF-Formeln, bei denen kein Variablenpaar in wesentlich mehr Abschnitten als im Durchschnitt vorkommt?

32

In dieser Frage bedeutet eine 3CNF-Formel eine CNF-Formel, bei der jede Klausel genau drei verschiedene Variablen enthält. Für eine Konstante 0 < s <1 ist Gap-3SAT s das folgende Versprechungsproblem:

Gap-3SAT s
Instanz : Eine 3CNF-Formel φ.
Ja-Versprechen : φ ist erfüllbar.
No-Versprechen : Keine Wahrheit Zuweisungen erfüllen mehr als s Bruchteil der Klauseln von φ.

Einer der äquivalenten Möglichkeiten , das berühmte PCP Theorem zu erklären [AS98, ALMSS98] ist , dass es eine Konstante existiert 0 < s <1 , so dass Gap-3SAT s ist NP-vollständig.

Wir sagen, dass eine 3CNF-Formel paarweise B-begrenzt ist, wenn jedes Paar unterschiedlicher Variablen in höchstens B- Sätzen vorkommt. Zum Beispiel kann eine 3CNF Formel ( x 1x 2x 4 ) ∧ (¬ x 1 ∨¬ x 3x 4 ) ∧ ( x 1x 3 ∨¬ x 5 ) ist , paarweise 2-begrenzt , aber nicht 1 paarweise -gebunden, weil zB das Paar ( x 1 , x 4 ) in mehr als einer Klausel vorkommt.

Frage . Haben existieren Konstanten B ∈ℕ, a > 0 und 0 < s <1 , so dass Gap-3SAT s NP-vollständig ist sogar für einen 3CNF Formel , die paarweise ist B -bounded und besteht aus mindestens einem 2 - Klauseln, wobei n ist die Anzahl der Variablen?

Die paarweise Begrenzung impliziert eindeutig, dass es nur O ( n 2 ) -Klauseln gibt. Zusammen mit der quadratischen Untergrenze für die Anzahl der Klauseln wird grob gesagt, dass in deutlich mehr Klauseln als im Durchschnitt kein Paar unterschiedlicher Variablen vorkommt.

Für Gap-3SAT ist bekannt, dass der spärliche Fall schwierig ist : Es gibt eine Konstante 0 < s <1, sodass Gap-3SAT s auch für eine 3CNF-Formel NP-vollständig ist, bei der jede Variable genau fünfmal vorkommt [Fei98]. Auf der anderen Seite, der dichte Fall ist einfach : Max-3SAT einen PTAS für eine 3CNF Formel mit Ω (zugibt n 3 ) verschiedenen Klauseln [AKK99], und deshalb Gap-3SAT s in diesem Fall ist in P für jede Konstante 0 < s <1. Die Frage fragt nach der Mitte dieser beiden Fälle.

Die obige Frage entstand ursprünglich in einer Studie über die Komplexität von Quantenrechnungen, genauer gesagt über einrundige interaktive Beweissysteme mit zwei Beweisen und verschränkten Beweismitteln ( MIP * (2,1) -Systeme). Aber ich denke, dass die Frage an sich schon interessant sein könnte.

Verweise

[AKK99] Sanjeev Arora, David Karger und Marek Karpinski. Polynomial Time Approximation Schemata für dichte Fälle von NP-harten Problemen. Journal of Computer and System Sciences , 58 (1): 193–210, Februar 1999. http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan und Mario Szegedy. Beweisüberprüfung und die Härte von Approximationsproblemen. Journal of the ACM , 45 (3): 501–555, Mai 1998. http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora und Shmuel Safra. Probabilistische Überprüfung von Beweisen: Eine neue Charakterisierung von NP. Journal of the ACM , 45 (1): 70–122, Januar 1998. http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige. Eine Schwelle von ln n zur Annäherung an die eingestellte Abdeckung. Journal of the ACM , 45 (4): 634–652, Juli 1998. http://doi.acm.org/10.1145/285055.285059

Tsuyoshi Ito
quelle
@ Tsuyoshi: Habe ich Recht, wenn ich annehme, dass über die anderen Zwischenfälle zwischen und m = Ω ( n 3 ) nichts bekannt ist ? m=O(n)m=Ω(n3)
András Salamon
1
@ András: Mir sind keine vorherigen Ergebnisse zu Zwischenfällen bekannt, aber ich denke, das ist ein Beweis für die NP-Vollständigkeit der folgenden Fälle. (1) Paarweise begrenzte -Klauseln, jedoch ohne Lücke. (2) mit einem Spalt, Ω ( n d ) Bestimmungen für jede Konstante d <3 ist , aber nicht notwendigerweise paarweise begrenzt. (3) Mit einer paarweise begrenzten Lücke sind Ω ( n d ) -Klauseln für jede Konstante d <2. Der Beweis von (1) ist eine einfache Reduktion von [Fei98]. Der Beweis von (2) verwendet einen Teil des Ergebnisses von Ailon und Alon 2007 . Der Beweis von (3) verwendet Expander. Ω(n2)Ω(nd)Ω(nd)
Tsuyoshi Ito
1
@ Tsuyoshi: Ich freue mich darauf, Ihre Zeitung zu lesen.
András Salamon
4
Keine Antwort, aber ich würde überprüfen , ob die Methoden zu bestätigen , dass eine zufällige 3CNF von m - Klauseln unerfüllbar ist , kann hier gelingt , dieses Problem zeigt einfach, zumindest wenn man die Solidität erforderlich Nähe von 7/8 zu sein. Diese Arbeiten sind erfolgreich, sobald es mehr als n 1,5 Klauseln gibt und sie wurden auf semi-zufällige Modelle erweitert (siehe Feige FOCS 07 zur Widerlegung geglätteter 3CNF). Es scheint jedoch, dass Tsuyoshi zeigte, dass auch der Fall von n 1.9 hier immer noch NP-hart ist. Vielleicht zeigt dies, dass diese Arbeiten nicht relevant sind. sn1.5n1.9
Boaz Barak
7
Boaz, Sie können eine Instanz von 3SAT immer "verdichten", indem Sie jede Variable durch Kopien ersetzen und dann jede Klausel durch M 3 Klauseln ersetzen und jede Variable in der ursprünglichen Klausel auf alle möglichen Arten durch Kopien ersetzen. Dies gibt Ihnen einen Fall, in dem der gleiche Bruchteil von Klauseln wie zuvor erfüllt werden kann, Sie jedoch von n Variablen und m Klauseln zu nM Variablen und m M 3 Klauseln wechseln, sodass Sie die Anzahl der Vorkommen ohne weitere Einschränkung beibehalten können die Solidität 7 / 8 + ε auch in Formeln mit N Variablen und N 2.999 Klauseln. MM3mM37/8+ϵNN2.999
Luca Trevisan

Antworten:

6

Keine vollständige Antwort, aber hoffentlich nah. Dies ist sehr nah an Lucas obigen Kommentaren. Ich glaube, die Antwort ist, dass es zumindest Konstanten B ∈ℕ, a > 0 und 0 < s <1 gibt, so dass Gap-3SAT s auch für eine 3CNF-Formel, die paarweise B- gebunden ist und aus besteht, NP-vollständig ist mindestens Klauseln, für jede konstante ε .an2ϵϵ

Der Beweis ist wie folgt. Betrachten wir ein GAP-3SAT s Instanz φ auf N Variablen , in denen jede Variable erscheint höchstens 5 - mal. Dies ist NP-vollständig, wie Sie in der Frage sagen.sϕN

Jetzt erstellen wir eine neue Instanz wie folgt:Φ

  1. Für jede Variable in φ , Φ hat n Variablen y i j .xiϕΦnyij
  2. Für jeden Satz von Indizes , a und b mit einem b , Φ hat ein Paar von Klauseln y i a¬ y i b¬ y i b und y i b¬ y i a¬ y i ein . Ich werde diese als Vergleichsklauseln bezeichnen, da sie sicherstellen, dass y i a = y i b, wenn sie erfüllt sind.iababΦyiayibyibyibyiayiayia=yib
  3. Für jede Klausel in beaufschlagende Variablen x i , x j und x k , für jeden a und b , Φ eine äquivalente Klausel enthalten, wobei x i ersetzt wird durch y i ein , x j ersetzt durch y j b und x k wird durch y k ( a + b ) ersetzt (hier erfolgt die Addition modulo n ). Ich werde diese als geerbte Klauseln bezeichnen.ϕxixjxkabΦxiyiaxjyjbxkyk(a+b)n

Die Gesamtanzahl der Variablen ist dann . Anmerkung Φ hat 2 N n 2 Vergleichsklauseln und 5m=nNΦ2Nn2geerbte Klauseln für insgesamt1153Nn2Klauseln. Nimmt mann=Nk, soergibt sichm=Nk+1und die Gesamtzahl der KlauselnC=11113Nn2n=Nkm=Nk+1 . Wir nehmenk=ϵ-1-1, alsoCm2-ϵ.C=113N2k+1=113m21k+1k=ϵ11Cm2ϵ

Als nächstes ist paarweise 8-fach begrenzt (maximal 2 aus den Vergleichsklauseln und 6 aus den geerbten Klauseln).Φ

Schließlich, wenn ist, sind mindestens ( 1 - s ) N Klauseln nicht erfüllt. Nun, wenn y i ay i b für irgendein a , b ist, dann sind mindestens n - 1 Klauseln nicht erfüllt. Beachten Sie, dass zur Erfüllung der ( 1 - s ) N nicht erfüllten Klauseln in einer Reihe von geerbten Klauseln für festes a , b dann die Zuweisung von Variablen y : a , y :ϕ(1s)Nyiayiba,bn1(1s)Na,by:a und y : ( a + b ) müssen sich um mindestens 1 - s unterscheideny:by:(a+b)Positionen, so dass mindestens1-sverbleiben1s5NVergleich nicht erfüllbare Klauseln. Dies muss für jede Wahl vonaundb gelten, also mindestens1-s1s5N(n1)abVergleichsklauseln müssen insgesamt nicht erfüllt sein, damit genügend ererbte Klauseln erfüllt sind. Betrachtet man jedoch das andere Extrem, bei dem alle Vergleichsklauseln erfüllt sind, so ist(1-s)Nn2=(1-s)m 2 k + 11s5Nn2=3(1s)11CKlauseln sind nicht erfüllbar. Mits=4+sbleibt also eine Lücke (wenn auch verringert)(1s)Nn2=(1s)m2k+1k+1=(1s)C .s=4+s5

Die Konstanten müssen wahrscheinlich noch einmal überprüft werden.

Joe Fitzsimons
quelle
Vielen Dank, Joe. Es tut mir leid, wenn dies nicht klar war, aber in dieser Frage müssen die drei Variablen in jeder Klausel alle verschieden sein, und daher können Vergleichsklauseln, wie sie geschrieben wurden, nicht verwendet werden. Ich habe einen Beweis für dieselbe Tatsache (paarweise begrenzte Ω (n ^ (2 − ε)) - Klauseln mit Lücke), die Expandergraphen verwendet, aber wenn dies ohne Verwendung von Expander bewiesen werden kann, bin ich sehr interessiert.
Tsuyoshi Ito
yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)
ϵk=k(n)
Ich werde die Details später genauer prüfen, aber die Idee, a, b und (a + b) zu verwenden, scheint zu funktionieren. Dies sollte mich vom expliziten Umgang mit Expandern befreien. Vielen Dank!
Tsuyoshi Ito
Kein Problem. Ich bin froh, dass ich helfen konnte.
Joe Fitzsimons