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)?

sat search-problem logspace

Biorąc pod uwagę zadowalający 2-CNF , możesz obliczyć szczególne zadowalające przypisanie za pomocą funkcji NL (to znaczy istnieje predykat który mówi, czy jest prawdziwe). Jeden ze sposobów na to opisano poniżej. Ja swobodnie korzystać z faktu, że NL zamknięte pod -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 , pozwolić być liczba literałach osiągalny z przez kierunek ruchu ścieżki na wykresie implikację 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 , z powodu symetrii skośnej wykresu implikacji. Zdefiniuj przypisanie , aby $\let\ob\overline \ob a^\to=a^\ot$ $\ob a^\ot=a^\to$ $e$

jeśli , to ; $a^\ot>a^\to$ $e(a)=1$
Jeśli , a następnie ; $a^\ot<a^\to$ $e(a)=0$
Jeśli niech być minimalne tak, że lub pojawia się w silnie połączony składnik (nie może być zarówno jako jest spe). Wpisz jeśli pojawi się , a 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 na wykresie implikacji: $e(\ob a)=\ob{e(a)}$ $a\to b$

Jeśli nie jest osiągalne z , to i . Zatem implikuje . $a$ $b$ $a^\ot<b^\ot$ $a^\to>b^\to$ $e(a)=1$ $e(b)=1$
W przeciwnym razie, i znajdują się w tym samym mocno połączonego składnika, a , . Zatem . $a$ $b$ $a^\ot=b^\ot$ $a^\to=b^\to$ $e(a)=e(b)$

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

— Emil Jeřábek wspiera Monikę
źródło

To jest miłe! Czy istnieje odniesienie?

— Ryan Williams,

Właśnie to ugotowałem, więc nie wiem, ale wygląda na to, że ktoś mógł to wcześniej zaobserwować. Moją inspiracją był argument, że topologiczne sortowanie zamówień częściowych można przeprowadzić w TC ^ 0, stąd ts wykresów acyklicznych w NL; to pozytywnie ma odniesienie, ale w tej chwili nie jestem w biurze, więc trudno mi go szukać.

— Emil Jeřábek wspiera Monikę

Wynik, w którym zadawanie zadaniowe można obliczyć w FNL, pojawia się z innym argumentem w Cookie, Kolokolova: Teoria drugiego rzędu dla NL oraz z nieco więcej szczegółów w Cookie, Nguyen: Logiczne podstawy złożoności dowodu. Przyznaję jednak, że nie mogę zrozumieć, jak to ma działać. O ile wiem, własność (307) pozostawiona jako ćwiczenie dla czytelnika w książce C&N jest po prostu fałszywa.

— Emil Jeřábek wspiera Monikę