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

15

Wenn , dann gibt es einen logspace Algorithmus , dass löst die Entscheidungsversion von 2-SAT ausgestattet .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?L=NL

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

Niel de Beaudrap
quelle

Antworten:

16

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ϕeP(ϕ,i)e(xi) -Reduktionen, daher sind NL-Funktionen unter Komposition geschlossen; Dies ist eine Folge von NL = coNL.AC0

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.ϕ(x1,,xn)aeineinϕeinein

Beachten Sie, dass und ¯ a = a , aufgrund Skew-Symmetrie der Implikation Graphen. Definieren Sie eine Zuordnung e damitein¯=einein¯=eine

  • wenn , dann ist e ( a ) = 1 ;ein>eine(ein)=1

  • wenn , dann ist e ( a ) = 0 ;a<ae(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=aixix¯iaϕe(a)=1xie(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(a¯)=e(a)¯ab

  • Wenn von b aus nicht erreichbar ist , dann a < b und a > b . Somit e ( a ) = 1 bedeutet , e ( b ) = 1 .aba<ba>be(a)=1e(b)=1

  • Ansonsten befinden sich und b in derselben stark verbundenen Komponente und a = b , a = b . Somit ist e ( a ) = e ( b ) .aba=ba=be(a)=e(b)

Daraus folgt, dass .e(ϕ)=1

Emil Jeřábek unterstützt Monica
quelle
Das ist nett! Gibt es eine Referenz?
Ryan Williams
2
Ich habe es gerade ausgedacht, damit ich es nicht weiß, aber es sieht einfach genug aus, dass jemand es früher beobachtet hat. Meine Inspiration war das Argument, dass die topologische Sortierung von Teilordnungen in TC ^ 0 durchgeführt werden kann, daher ts von azyklischen Graphen in NL; Das hat einen positiven Bezug, aber ich bin im Moment nicht im Büro, daher fällt es mir schwer, danach zu suchen.
Emil Jeřábek unterstützt Monica am
1
Das Ergebnis, dass befriedigende Zuordnungen in FNL berechnet werden können, erscheint mit einem anderen Argument in Cook, Kolokolova: Eine Theorie zweiter Ordnung für NL, und mit etwas mehr Details in Cook, Nguyen: Logische Grundlagen der Beweiskomplexität. Ich gebe jedoch zu, dass ich nicht herausfinden kann, wie es funktionieren soll. Soweit ich das beurteilen kann, ist das Eigentum (307), das dem Leser im C & N-Buch als Übung überlassen wird, einfach falsch.
Emil Jeřábek unterstützt Monica am