Złożoność wersji wyszukiwania 2-SAT przy założeniu

Jeśli , a następnie jest algorytm logspace który rozwiązuje wersja decyzja 2-SAT.$\mathsf{L = NL}$

• Czy wiadomo, że sugeruje, że istnieje algorytm przestrzeni logicznej, który pozwala uzyskać zadowalające przypisanie , jeśli dane wejściowe są zadowalające dla 2-SAT?$\mathsf{L = NL}$

• Jeśli nie, to co z algorytmami wykorzystującymi przestrzeń sublinearną (w liczbie klauzul)?

Biorąc pod uwagę zadowalający 2-CNF , możesz obliczyć szczególne zadowalające przypisanie e za pomocą funkcji NL (to znaczy istnieje predykat P P ( ϕ , i ), który mówi, czy e ( x i ) jest prawdziwe). Jeden ze sposobów na to opisano poniżej. Ja swobodnie korzystać z faktu, że NL zamknięte pod C 0 -reductions stąd NL-funkcje są zamknięte pod kompozycji; jest to konsekwencja NL = coNL.$\phi$$e$$P(\phi,i)$$e(x_i)$$\mathrm{AC}^0$

Niech będzie zadowalającym 2-CNF. Dla każdego dosłownym A , pozwolić → być liczba literałach osiągalny z przez kierunek ruchu ścieżki na wykresie implikację cp i ← liczba literałach z których jest nieosiągalny. Oba są obliczalne w NL.$\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$

Zauważ, że i ¯ a ← = a → , z powodu symetrii skośnej wykresu implikacji. Zdefiniuj przypisanie e , aby$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• jeśli , to e ( a ) = 1 ;$a^\ot>a^\to$$e(a)=1$

• Jeśli ← < → , a następnie e ( ) = 0 ;$a^\ot<a^\to$$e(a)=0$

• Jeśli ← = → niech i być minimalne tak, że x I lub Ż x i pojawia się w silnie połączony składnik (nie może być zarówno jako φ jest spe). Wpisz e ( a ) = 1, jeśli pojawi się x i , a e ( a ) = 0 w przeciwnym razie.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

Symetria skośna wykresu sugeruje, że , stąd jest to dobrze zdefiniowane przypisanie. Ponadto dla dowolnej krawędzi a → b na wykresie implikacji:$e(\ob a)=\ob{e(a)}$$a\to b$

• Jeśli nie jest osiągalne z b , to a ← < b ← i a → > b → . Zatem e ( a ) = 1 implikuje e ( b ) = 1 .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• W przeciwnym razie, i b znajdują się w tym samym mocno połączonego składnika, a ← = b ← , → = b → . Zatem e ( a ) = e ( b ) .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Wynika z tego, że .$e(\phi)=1$