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

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 ₁ ∨ x ₂ ∨ x ₄ ) ∧ (¬ x ₁ ∨¬ x ₃ ∨ x ₄ ) ∧ ( x ₁ ∨ x ₃ ∨¬ x ₅ ) ist , paarweise 2-begrenzt , aber nicht 1 paarweise -gebunden, weil zB das Paar ( x ₁ , x ₄ ) 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 ² - Klauseln, wobei n ist die Anzahl der Variablen?

Die paarweise Begrenzung impliziert eindeutig, dass es nur O ( n ² ) -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 ³ ) 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

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 ε .$an^{2-\epsilon}$$\epsilon$

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$$\phi$$N$

Jetzt erstellen wir eine neue Instanz wie folgt:$\Phi$

1. Für jede Variable in φ , Φ hat n Variablen y i j .$x_i$$\phi$$\Phi$$n$$y_{ij}$
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.$i$$a$$b$$a\neq b$$\Phi$$y_{ia}∨￢y_{ib}∨￢y_{ib}$$y_{ib}∨￢y_{ia}∨￢y_{ia}$$y_{ia} = y_{ib}$
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.$\phi$$x_i$$x_j$$x_k$$a$$b$$\Phi$$x_i$$y_{ia}$$x_j$$y_{jb}$$x_k$$y_{k(a+b)}$$n$

Die Gesamtanzahl der Variablen ist dann . Anmerkung Φ hat 2 N n 2 Vergleichsklauseln und $m = nN$$\Phi$$2Nn^2$geerbte Klauseln für insgesamt$\frac{5}{3}Nn^2$Klauseln. Nimmt mann=Nk, soergibt sichm=Nk+1und die Gesamtzahl der KlauselnC=$\frac{11}{3}Nn^2$$n = N^k$$m = N^{k+1}$ . Wir nehmenk=ϵ-1-1, alsoC∝m2-ϵ.$C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$$k = \epsilon^{-1} - 1$$C \propto m^{2-\epsilon}$

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

Schließlich, wenn ist, sind mindestens ( 1 - s ) N Klauseln nicht erfüllt. Nun, wenn y i a ≠ y 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 $\phi$$(1-s)N$$y_{ia} \neq y_{ib}$$a,b$$n-1$$(1-s)N$$a,b$$y_{:a}$ und y : ( a + b ) müssen sich um mindestens 1 - $y_{:b}$$y_{:(a+b)}$Positionen, so dass mindestens1-sverbleiben$\frac{1-s}{5}N$Vergleich nicht erfüllbare Klauseln. Dies muss für jede Wahl vonaundb gelten, also mindestens≈1-$\frac{1-s}{5}N(n-1)$$a$$b$Vergleichsklauseln 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 + $\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$Klauseln sind nicht erfüllbar. Mits′=4+sbleibt also eine Lücke (wenn auch verringert)$(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$ .$s' = \frac{4+s}{5}$

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