Berechnung von Informationen zu Max-3SAT

Für eine 3CNF Formel lassen in beliebiger Zuordnung zur maximalen Anzahl der Klauseln erfüllt sein . Es ist bekannt, dass Max-3SAT schwer zu approximieren ist (abhängig von P ≠ NP), dh es gibt keinen Polyzeitalgorithmus, dessen Eingabe eine 3CNF-Formel ist und dessen Ausgabe die Zahl so dass innerhalb von a liegt multiplikativer Faktor von , wobei eine absolute positive Konstante ist.M ( C ) C C M ' M ( C ) 1 + c M ' c > $C$$M(C)$$C$$C$$M'$$M(C)$$1+c$$M'$$c>0$

Ich glaube, dass es auch NP-schwierig ist, für einen konstanten Modul zu berechnen . Ich frage mich, ob die folgende allgemeine Verallgemeinerung dieser beiden Tatsachen zutrifft: Es gibt keinen Polyzeitalgorithmus, dessen Eingabe eine 3CNF-Formel mit Sätzen und eine Folge von Hinweisbits ist und dessen Ausgabe . Hier ist eine absolute Konstante. In einfachen Worten gibt es keinen Algorithmus, der Informationsbits von berechnet .$M(C) \bmod p$$p$$C$$N$$\log_2 N-B$$M(C)$$B$$B$$M(C)$

Ich entschuldige mich, wenn die Frage eine bekannte Antwort hat, denn ich bin im Hintergrund kein Komplexitätstheoretiker.

Hier ist ein Argument, dass, wenn Sie Max 3SAT für eine m-Klausel-Instanz mit einer konstanten Anzahl von Ratschlägen lösen könnten, die Polynomhierarchie zusammenbrechen würde.

Beheben Sie ein NP-vollständiges Problem L. Aus Cooks Theorem kennen wir eine Transformation f () von Eingaben x für L in 3SAT-Formeln f (x), so dass

1) Wenn dann ist$x\in L$$M(f(x)) = m$

2) Wenn dann ist$x\in L$$M(f(x)) = m-1$

Dabei ist die Anzahl der Klauseln in .$m$$f(x)$

Wir haben auch ein Theorem von Kadin, das besagt, dass, wenn Eingänge eines NP-vollständigen Problems gegeben sind, Sie einen polynomiellen Zeitalgorithmus haben, der Anfragen an ein NP-Orakel stellt und das bestimmt richtige Antwort auf die NP-Probleme , dann kollabiert die Polynomhierarchie.x 1 , … , x k ≤ k - 1 k x i ∈ ? $k$$x_1,\ldots,x_k$$\leq k-1$$k$$x_i \in ? L$

Angenommen, wir haben einen Algorithmus, der Max SAT für m-Klausel-Eingaben mit k Ratschlägen löst. Wir werden Hastads Ergebnis verwenden, um einen Algorithmus wie in der Prämisse von Kadins Theorem zu konstruieren.

Start aus dem Eingängen Problem . Wenden Sie auf jeden von ihnen den Satz von Cook an. Nach einer gewissen Normalisierung (durch Zuweisen von Gewichten zu den Klauseln oder durch Duplizieren derselben, wenn wir keine Gewichte verwenden möchten) konstruieren wir Formeln wobei für ein bestimmtes :× 1 , … , x K L K F 1 , … , F K$K=2^k+1$$x_1,\ldots,x_K$$L$$K$$F_1,\ldots,F_K$$m$

1) wenn und wenn nicht× 1 ≤ L M ( F 1 ) = m - $M(F_1)= m-1$$x_1 \in L$$M(F_1) = m-2$

2) falls und falls nicht× 2 ≤ L M ( F 2 ) = m ≤ ( m - 2 $M(F_2) = m\cdot (m-1)$$x_2 \in L$$M(F_2) = m\cdot (m-2)$

...

k) wenn und andernfallsx K ≤ L M ( F K ) = m K - 1 ≤ ( m - 2 $M(F_K) = m^{K-1} \cdot (m-1)$$x_K\in L$$M(F_K) = m^{K-1} \cdot (m-2)$

Nun nehmen Sie die Vereinigung der Formeln, die über disjunkte Variablen - Sets gebaut wurden, und nennt es . Wir haben also und können die Antwort auf die Probleme "ablesen" durch Betrachten der Basis- Darstellung von . Wenn wir mit Ratschlägen berechnen können , bedeutet dies, dass wir Werte finden können, von denen einer . Wir können dann ein NP-Orakel nicht adaptiv fragen, ob für jeden der KandidatenwerteM ( F ) = M ( F 1 ) + ⋯ + M ( F k ) K x i ∈ ? L m M ( F ) M ( F ) k 2 k M ( F ) M ( F ) ≥ n i n 1 , … , n 2 k 2 k + 1 $F$$M(F) = M(F_1) + \cdots + M(F_k)$$K$$x_i \in? L$$m$$M(F)$$M(F)$$k$$2^k$$M(F)$$M(F) \geq n_i$$n_1,\ldots,n_{2^k}$wir haben generiert. So konnten wir Fälle von NP-vollständigen Problemen lösen, indem wir nicht-adaptive Abfragen an ein NP-Orakel stellten, was impliziert, dass die Polynomhierarchie zusammenbricht.$2^k+1$$2^k$

Unter Verwendung von Hastads Theorem anstelle von Cooks Theorem ist es möglich, die Größe von nach anstelle von , so dass es möglich ist, nach und die Anzahl der Hinweisbits nach zu verschieben . Es scheint wirklich schwierig zu verstehen, was passiert, wenn Sie Ratschläge erhalten.O ( 1 ) k ⋅ m m k k log m log log m log m - O ( 1 $F$$O(1)^k \cdot m$$m^k$$k$$\log m$$\log\log m$$\log m - O(1)$

Herausgegeben um hinzuzufügen: Krentel ( Die Komplexität von Optimierungsproblemen . J. Comput. Syst. Sci. 36 (3): 490-509 (1988) ) hat bewiesen, dass die Berechnung des Wertes des Optimums des Maximum-Clique-Problems für vollständig ist , die Klasse von Funktionen, die in Polynomzeit mit -Anfragen an ein NP-Orakel berechnet werden können . Die Vollständigkeit ist unter „einer Abfrage Reduzierungen“ , in der Funktion f Funktion g reduzierbar ist , wenn man schreiben kann für Polynom berechenbar und . Vermutlich das gleiche gilt für Max Clique: Wenn Max Clique nun einen polynomialen Zeitalgorithmus hätte, der eine Liste von O ( l o g n ) f ( x ) = r 1 ( g ( r 2 ( x ) ) r 1 r 2 m o ( 1 ) F P N P [ o ( l o g n ) $FP^{NP[O(log n)]}$$O(log n)$$f(x) = r_1(g(r_2(x))$$r_1$$r_2$$m^{o(1)}$Mögliche Werte wären , da Sie die binäre Suche verwenden könnten, um das Optimum mit einer Anzahl von Abfragen zu finden, die logarithmisch der Listengröße sind.$FP^{NP[o(logn)]}$

Wenn wir nun hätten, hätten wir definitiv , der Spezialfall für Entscheidungsprobleme, und der durch Ergebnisse von Wagner (Verbesserung eines Ergebnisses von Kadin, das für eine konstante Anzahl von Abfragen gilt) bekannt ist, um die Polynomhierarchie zu kollabieren. Aber ich denke, dass es bekannt sein könnte, dass tatsächlich P = NP implizieren würde. Aber auf jeden Fall sollten die Ergebnisse von Krentel und Kadin-Wagner ausreichen, um das Ergebnis von Andy Drucker erneut zu belegen. Nun frage ich mich, ob es tatsächlich der gleiche Beweis ist, das heißt, ob das Ergebnis von Fortnow-Van Melkebeek explizit oder implizit über ein Argument "Simulieren von NP-Abfragen mit weniger NP-Abfragen" funktioniert. P N P [ O ( l o g n ) ] = P N P [ o ( l o g n) ) ] F P N P [ O ( l $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$$P^{NP[O(log n)]} = P^{NP[o(log n)]}$$FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$

Ein gutes Umfragepapier, das erklärt, was mit Optimierungsproblemen und begrenzten Abfrageklassen los ist:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

Ich möchte einen Grund nennen, warum es schwierig ist, die NP-Härte dieses Problems zu beweisen.

In einem Kommentar zur Frage hat Luca Trevisan das Problem auf eine nette Art und Weise umformuliert: Ist das folgende Problem in Polynomzeit für jede Konstante k lösbar ? Bei einer CNF-Formel C mit m- Klauseln werden höchstens m / k ganze Zahlen ausgegeben, sodass eine davon gleich M ( C ) ist. Hier ist k mit B durch k = 2 ^{B verwandt} .

Verlangen wir jedoch mehr. Wir betrachten nämlich das folgende Problem: Wenn eine CNF-Formel C gegeben ist , geben wir zwei ganze Zahlen aus, so dass eine von ihnen gleich M ( C ) ist. Wir bezeichnen dieses Problem mit Π. Das Problem Π ist mindestens so schwierig wie das ursprüngliche Problem. Wenn das ursprüngliche Problem NP-hart ist, muss Π auch NP-hart sein.

Beachten Sie, dass Π ein Beziehungsproblem ist. Eine der einfachsten Arten von Reduktionen, die verwendet werden können, um ein Problem L auf ein Beziehungsproblem Π zu reduzieren, ist eine Levin-Reduktion in Polynomzeit, die ein Spezialfall einer Turing-Reduktion in Polynomzeit ist, bei der die Reduktion das Orakel nur für Π aufruft Einmal.

Wir behaupten, dass P ^{Π [1]} = P. Dies impliziert offensichtlich, dass NP⊈P ^{Π [1] ist, es} sei denn, P = NP, das heißt, Π ist unter polynomieller Levinreduzierbarkeit nicht NP-hart, es sei denn, P = NP.

Beweis . Sei L ∈P ^{Π [1]} , oder mit anderen Worten, es gibt eine Levinreduktion von L nach Π. Dies bedeutet, dass es ein Paar ( f , g ) einer Polynomzeit-berechenbaren Funktion f gibt : {0,1} ^* → {0,1} ^*, die jede Instanz x des Problems L auf eine CNF-Formel f ( x abbildet ) und ein polynomzeitberechenbares Prädikat g : {0,1} ^* × ℕ × ℕ → {0,1} mit g ( x , i , j ) = L( x ) wenn entweder i oder j gleich M ist ( f ( x )). (Hier ist L ( x ) = 1, wenn x eine Ja-Instanz von L ist, und L ( x ) = 0, wenn x eine Nein-Instanz ist.)

Daraus konstruieren wir wie folgt einen Polynom-Zeit-Algorithmus für L. Sei x eine Eingabe.

1. Lassen Sie C = f ( x ), und lassen Sie m die Anzahl der Klauseln in sein C .
2. Suchen Sie eine i ∈ {0,…, m }, so dass der Wert g ( x , i , j ) unabhängig von j ∈ {0,…, m } konstant ist .
3. Gib diese Konstante g ( x , i , 0) aus.

In Schritt 2 existiert ein solches i immer, weil i = M ( f ( x )) die Bedingung erfüllt. Außerdem kann dieser Algorithmus keine falsche Antwort ausgeben, da g ( x , i , M ( f ( x ))) die richtige Antwort sein muss. Daher löst dieser Algorithmus L korrekt. QED .

Wenn ich mich nicht täuscht, kann die gleiche Idee verwendet werden , um zu beweisen , dass P ^{Π [ k ( n )]} ⊆DTIME [ n ^{O ( k ( n ))} ]. Dies impliziert, dass NP⊈P ^{Π [ k ]} für jede Konstante k gilt, es sei denn, P = NP, und dass NP⊈P ^{Π [polylog], es} sei denn, NP⊆DTIME [2 ^polylog ]. Diese Idee allein scheint jedoch nicht auszuschließen, dass Π unter polynomialer Turing-Reduzierbarkeit NP-hart ist.

Ich glaube, dass wir zeigen können:

Anspruch. Es gibt einen Wert , sodass Folgendes zutrifft. Angenommen, es gibt einen deterministischen Polyzeitalgorithmus , der bei einer Klausel 3-SAT-Instanz eine Liste von höchstens Werten ausgibt , so dass ; dann kollabiert die Polynomhierarchie.m ≤ S m $0 < c < 1$$m$$\phi$$S$$m^c$$M(\phi) \in S$

Der Proof verwendet die Ergebnisse von Fortnow und Santhanam zur Unmöglichkeit der Instanzkomprimierung aus dem Papier http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

Insbesondere, wenn man sich den Beweis von Thm 3.1 ansieht, glaube ich, dass man das Folgende extrahieren kann (das werde ich bald noch einmal überprüfen):

"Theorem" [FS]. Es gibt ganze Zahlen so dass Folgendes zutrifft. Angenommen, man kann in deterministischer Polyzeit ein OR von Booleschen Formeln (jeweils mit der Länge und disjunkten Variablenmengen) in ein OR von Formeln (wiederum variabel-disjunkt und ) transformieren der Länge ), Erhalt der Erfüllbarkeit / Unerfüllbarkeit des OP. Dann und die .n d ≤ n n d ' ≤ n N P ⊆ c o N P / p o l $0 < d' < d$$n^d$$\leq n$$n^{d'}$$\leq n$$\mathsf{NP} \subseteq \mathsf{coNP/poly}$

Der Beweis unserer Behauptung wird eine Reduktion von der im obigen Theorem [FS] erwähnten OR-Komprimierungsaufgabe auf das Problem der Listenberechnung . Angenommen, ist eine Liste von Formeln, deren ODER wir komprimieren möchten.ψ 1 , … , ψ n $M(\phi)$$\psi_1, \ldots, \psi_{n^d}$

Erster Schritt: Definieren Sie eine polynomgroße Schaltung für Eingabezeichenfolgen . Hier codiert der String eine Zuweisung zu , und codiert eine Zahl zwischen und .( v , y 1 , … , y n d ) y i ψ i v ∈ { 0 , 1 } d log n + 1 0 n $\Gamma$$(v, y_1, \ldots, y_{n^d})$$y_i$$\psi_i$$v \in \{0, 1\}^{d \log n + 1}$$0$$n^d$

Wir haben accept, wenn entweder oder .v = 0 ψ v ( y v ) = $\Gamma$$v = 0$$\psi_v(y_v) = 1$

Nun sei der Maximalwert , so dass die eingeschränkte Schaltung erfüllbar ist. (Diese Menge ist immer mindestens 0).v Γ ( v , ⋅ , … , ⋅ $M^*(\Gamma)$$v$$\Gamma(v, \cdot, \ldots, \cdot)$

Angenommen, wir können effizient eine Liste möglicher Werte für erstellen . Dann ist die Behauptung, dass wir in unserer Liste alle wegwerfen können, für die ; Die sich ergebende Liste enthält eine erfüllbare Formel, falls dies die ursprüngliche tat. Ich hoffe, das wird durch die Inspektion klar.M ∗ ( Γ ) ψ 1 , … , ψ n d ψ i i ∉ $S$$M^*(\Gamma)$$\psi_1, \ldots, \psi_{n^d}$$\psi_i$$i \notin S$

Fazit: Wir können keine Liste von möglichen Werten für zuverlässig erstellen , wenn die Polyhierarchie nicht zusammenbricht.≤ n d ' M * ( Γ $S$$\leq n^{d'}$$M^*(\Gamma)$

Zweiter Schritt: Wir reduzieren das Problem der Listenberechnung auf das Problem der Listenberechnung für 3-SAT-Instanzen .M ( ϕ ) $M^*(\Gamma)$$M(\phi)$$\phi$

Dazu führen wir zuerst Cooks Reduktion auf , um eine 3-SAT-Instanz der Größe . hat dieselbe Variablenmenge wie , zusammen mit einigen Hilfsvariablen. Für unsere Zwecke ist am wichtigsten , wenn erfüllt werden kann.φ 1 m = p o l y ( n d ) φ 1 Γ φ 1 ( v , ⋅ ) Γ ( v , ⋅ $\Gamma$$\phi_1$$m = poly(n^d)$$\phi_1$$\Gamma$$\phi_1(v, \cdot)$$\Gamma(v, \cdot)$

Wir nennen die "starken Einschränkungen". Wir geben jeder dieser Bedingungen ein Gewicht von (indem wir doppelte Bedingungen hinzufügen). 2 $\phi_1$$2m$

Dann fügen wir eine Menge von "schwachen Nebenbedingungen" hinzu, die eine Präferenz dafür hinzufügen, dass der Index (definiert in Schritt 1) ​​so hoch wie möglich ist. Es gibt eine Einschränkung für jedes Bit von , nämlich . Wir lassen das wertigste Bit von eine Gewichtsbeschränkung von . Da Länge , können diese Gewichtungen als Ganzes gebildet werden (wir müssen nur auffüllen, damit eine Potenz von 2 ist). v v t v [ v t = 1 ] t v m / 2 t - 1 v d log n + 1 $\phi_2$$v$$v_t$$v$$[v_t = 1]$$t$$v$$m/2^{t-1}$$v$$d \log n + 1$$m$

Schließlich sei das Ergebnis unserer Reduktion.$\phi = \phi_1 \wedge \phi_2$

Für die Analyse von sei die Variablenmenge von mit wie zuvor. Man beachte zunächst, dass man bei einer gegebenen Zuordnung zu den Wert von aus der Menge (Gesamtgewicht der durch erfüllten -Regelungen ) ableiten kann . Dies ergibt sich aus dem hierarchischen Aufbau der Constraint-Gewichte (ähnlich einer Technik aus Lucas Antwort). In ähnlicher Weise wird der maximal erreichbare Wert durch eine Einstellung , die alle starken Einschränkungen erfüllt, und wo (vorbehaltlich dieser)( v , z ) φ v ( v , z ) v N ( v , z ) = φ v , z M ( φ ) ( v , z ) , v v Γ ( v , ⋅ ) M * ( Γ ) v = Γ ( v , ⋅ $\phi$$(v,z)$$\phi$$v$$(v, z)$$v$$N(v, z) =$$\phi$$v, z$
$M(\phi)$$(v, z)$$v$ist so groß wie möglich. Dieses ist der größte Index, für den erfüllt werden kann, nämlich . (Beachten Sie, dass es immer möglich ist, durch Setzen von all-0 alle starken Bedingungen zu erfüllen, da in diesem Fall erfüllt werden kann.)$v$$\Gamma(v, \cdot)$$M^*(\Gamma)$$v =$$\Gamma(v, \cdot)$

Daraus folgt, dass wir, wenn wir eine Liste möglicher Werte von , eine Liste von ableiten können mögliche Werte von . Wir können also nicht sofern die Polyhierarchie nicht zusammenbricht. Dies ergibt die Behauptung, da .M ( ϕ ) | S | M ∗ ( Γ ) | S | ≤ n d ' n d ' = m Ω ( 1 $S$$M(\phi)$$|S|$$M^*(\Gamma)$$|S| \leq n^{d'}$$n^{d'} = m^{\Omega(1)}$