Komplexität der von 2-SAT unter der Annahme von

Wenn , dann gibt es einen logspace Algorithmus , dass löst die Entscheidungsversion von 2-SAT ausgestattet .$\mathsf{L = NL}$

• Ist bekannt, dass impliziert, dass es einen Logspace-Algorithmus gibt, um eine zufriedenstellende Zuweisung zu erhalten , wenn eine zufriedenstellende 2-SAT-Instanz als Eingabe gegeben wird?$\mathsf{L = NL}$

• Wenn nicht, was ist mit Algorithmen, die sublinearen Raum verwenden (in der Anzahl der Klauseln)?

Wenn ein erfüllbarer 2-CNF , können Sie eine bestimmte erfüllende Zuweisung e durch eine NL-Funktion berechnen ( dh es gibt ein NL-Prädikat P ( ϕ , i ) , das Ihnen sagt, ob e ( x i ) wahr ist). Ein Weg, dies zu tun, wird unten beschrieben. Ich werde die Tatsache, dass NL unter A C geschlossen ist, frei nutzen$\phi$$e$$P(\phi,i)$$e(x_i)$ -Reduktionen, daher sind NL-Funktionen unter Komposition geschlossen; Dies ist eine Folge von NL = coNL.$\mathrm{AC}^0$

Sei ein erfüllbarer 2-CNF. Für jedes Literal a sei a → die Anzahl der Literale, die von a über einen gerichteten Pfad im Implikationsgraphen von ϕ erreichbar sind , und a ← die Anzahl der Literale, von denen aus a erreichbar ist. Beide sind in NL berechenbar.$\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$

Beachten Sie, dass und ¯ a ← = a → , aufgrund Skew-Symmetrie der Implikation Graphen. Definieren Sie eine Zuordnung e damit$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• wenn , dann ist e ( a ) = 1 ;$a^\ot>a^\to$$e(a)=1$

• wenn , dann ist e ( a ) = 0 ;$a^\ot<a^\to$$e(a)=0$

• wenn , lassen i minimal sein , so dass x i oder ¯ x i in den stark verbundenen Komponente erscheint ein (es kann nicht beide, da φ erfüllbar ist). Setze e ( a ) = 1, wenn x i erscheint, und e ( a ) = 0, wenn nicht.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

Die Skew-Symmetrie des Graphen, der impliziert , , daher ist dies eine gut definierte Zuordnung. Außerdem gilt für jede Kante a → b im Implikationsgraphen:$e(\ob a)=\ob{e(a)}$$a\to b$

• Wenn von b aus nicht erreichbar ist , dann a ← < b ← und a → > b → . Somit e ( a ) = 1 bedeutet , e ( b ) = 1 .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• Ansonsten befinden sich und b in derselben stark verbundenen Komponente und a ← = b ← , a → = b → . Somit ist e ( a ) = e ( b ) .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Daraus folgt, dass .$e(\phi)=1$