Czy istnieje niedeterministyczny algorytm liniowego czasu dla CNF-SAT?

19

Problem decyzyjny CNF-SAT można opisać następująco:

Dane wejściowe: wzór logiczny ϕ w spójnej postaci normalnej.

Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕ ?

Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema taśmami .

Uważam, że istnieje NTM, który rozwiązuje CNF-SAT etapami npoli(log(n)) .

Pytanie: Czy istnieje NTM, który rozwiązuje CNF-SAT w krokach O(n) ?

Wszelkie odnośne referencje są doceniane, nawet jeśli zapewniają jedynie niedeterministyczne podejścia zbliżone do liniowego.

Michael Wehar
źródło
5
Santhanam w 2001 roku napisał: „SAT NTIME ( n polylog ( n ) ), wynik wynikający z faktów, że SAT może być zaakceptowany w czasie n polylog ( n ) na NRAM i że istnieje skuteczna symulacja NRAM przez NTM , z powodu Gurewicza i Szelacha ”. Więc nie wydaje mi się, że SAT NTIME ( n ) jest znana. (Odniesienie dotyczy LNCS 363 z 1989 r.)n(n)n(n)n
András Salamon
5
@Boson, załóż, że otrzymujesz nie tylko zadowalające zadanie, ale także pełne obliczenie formuły. Jak sprawdziłbyś, czy jest to prawidłowe obliczenie w czasie liniowym? Nie jest jasne, nawet możesz to zrobić dla 3CNF-SAT, ponieważ musisz skakać, aby sprawdzić przypisanie do zmiennych.
Kaveh
4
@Boson Nie jest jasne, czy można sprawdzić, czy przypisanie spełnia formułę w czasie liniowym za pomocą TM z dwiema taśmami. Prawdopodobnie będziesz musiał wielokrotnie przesuwać głowę do przodu i do tyłu. Jeśli masz skuteczne podejście do tej weryfikacji, daj mi znać. :)
Michael Wehar
5
Tylko uwaga: jeśli zmienne są reprezentowane jako jednoargumentowe (SAT wciąż jest NPC), to istnieje dwuwarstwowy NTM, który rozpoznaje niezrównanie zadowalającą formułę w 2 |φkroki2)|φ|
Marzio De Biasi
3
@MichaelWehar jeśli używasz sortowania zliczającego, możesz posortować n kluczy z zakresu [0, k] w czasie O (n + k) w rozsądnym modelu o swobodnym dostępie (np. Maszyna Turinga o dostępie swobodnym, gdzie możesz wziąć O (log) n) czas na spisanie indeksu, a następnie przejście do tego indeksu taśmy w 1 kroku). Jeśli kodujesz każdy literał jako ciąg bitów (log n + 1), całkowita liczba klauzul i zmiennych wynosi co najwyżej O (n / log n), w którym to przypadku operacje czasu O (log n) na wszystkich literałach są w porządku. Rozszerzenie na dwie taśmy TM nie jest proste, przynajmniej z sortowaniem zliczającym.
Ryan Williams

Odpowiedzi:

5

To tylko rozszerzony komentarz. Kilka razy temu zapytałem (siebie :-), jak szybko może być wielopasmowy NTM, który akceptuje (rozsądnie zakodowany) język NP-zupełny. Wpadłem na ten pomysł:

3-SAT pozostaje NP-kompletny, nawet jeśli zmienne są reprezentowane w jedności. W szczególności możemy przekonwertować klauzulę - załóżmy - o dowolnej formule 3-SAT φ na n zmiennych i klauzulach mw sekwencji znaków nad alfabetem Σ = { + , - , 1 }, w którym każde wystąpienie zmiennej jest reprezentowane jako jednoargumentowe:(xja¬xjotxk)φnmΣ={+,,1}

+1i0,1j,+1k

Na przykład można przekonwertować na:(x2x3+4)

+110-1110+11110

Możemy więc przekonwertować wzór 3-SAT na równoważny ciąg U ( φ i ) łączący jego zdania. Język L U = { U ( φ i ) φ iφiU(φi) jest NP-kompletny.LU={U(φi)φi3SAT}

NTM z 2 taśmami może zdecydować, czy ciąg w czasie 2 | x | w ten sposób.xLU2|x|

  • pierwsza głowa skanuje dane wejściowe od lewej do prawej iz wewnętrzną logiką śledzi, kiedy wchodzi lub wychodzi z klauzuli lub osiąga koniec formuły. Ilekroć znajdzie znak lub - , druga głowa zaczyna się przesuwać w prawo na 1 i, który reprezentuje x i . Na końcu 1 i , jeśli druga głowa ma wartość 0, wówczas zgaduje wartość prawdy + lub - (wykonuje przypisanie) i zapisuje ją na drugiej taśmie; jeśli znajdzie znak + lub -, wówczas tej zmiennej przypisano już wartość;+1ixi1i0++
  • w obu przypadkach, używając wewnętrznej logiki, NTM dopasowuje wartość prawdy pod drugą głową (przypisanie) do ostatnio widzianego lub - ; jeśli się zgadzają, klauzula jest spełniona;+
  • wtedy druga głowa może powrócić do skrajnie prawej komórki;
  • z wewnętrzną logiką NTM może śledzić, czy wszystkie klauzule są spełnione, gdy pierwsza głowa przesuwa się w kierunku końca wejścia.

Przykład:

Tape 1 (formula)    Tape 2 (variable assignments)
+110-1110+11110...  0000000000000...
^                   ^
+110-1110+11110...  0000000000000...
 ^                  ^
+110-1110+11110...  0000000000000...
  ^                  ^
+110-1110+11110...  0+00000000000... first guess set x2=T; matches +
  ^                  ^               so remember that current clause is satisfied
+110-1110+11110...  0+00000000000... 
  ^                  ^
...
+110-1110+11110...  0+00000000000... 
    ^               ^
...
+110-1110+11110...  0++0000000000... second guess set x3=T
       ^              ^              don't reject because current
                                     clause is satisfied (and in every
                                     case another literal must be parsed)

Czas można skrócić do jeśli dodamy kilka zbędnych symboli do reprezentacji klauzuli:|x|

+1i0i,1j0j,+1k0k...+++

( oznacza koniec formuły)+++

W ten sposób druga głowa może powrócić do lewej komórki, podczas gdy pierwsza skanuje część . Używanie ++ jako separatora klauzul i +++0i+++++ jako znacznika końca formuły, możemy użyć tej samej reprezentacji dla formuł CNF z dowolną liczbą literałów na klauzulę.

Marzio De Biasi
źródło
1
Jednoznaczna reprezentacja jest jednoznaczna, więc można użyć 0/1 dla +/-, podając 011011110111110 jako pierwszy przykład. 00 następnie służy jako znacznik końca klauzuli, ponieważ 000 nie może wystąpić w przeciwnym razie (jeśli 00 występuje, to jest to znacznik końcowy zmiennej i następny znak, więc następnym symbolem musi być 1). Pojedyncza taśma robocza zawiera odgadnięte przyporządkowanie bitowe do zmiennych v . Kiedy zmienna jest czytana, głowa taśmy roboczej przesuwa się do przodu, a następnie jest cofana do początku, gdy widoczne jest 0, czyli co najwyżej 2 kroki dla każdego bitu wejścia. vv2)
András Salamon,
2
Innymi słowy, nawet NDTM z jednokierunkową taśmą wejściową i pojedynczą taśmą roboczą wykorzystuje co najwyżej kroków dla Unary SAT zakodowanego alfabetem boolowskim. 2n
András Salamon,
1
Aby uczynić rzeczy jeszcze bardziej uporządkowanymi, można dodatkowo wymagać, aby dane wejściowe zawierały najpierw przedrostek z liczbą zmiennych określonych w unary. Pozwala to na budowanie domysłów podczas czytania prefiksu. Jest to zatem rodzaj „jednoargumentowego kodowania SATLIB”, o wielkości co najwyżej kwadratowej w standardowej instancji SAT, o ile każda zmienna pojawia się co najmniej raz w formule, a zmienne są ponumerowane od 0 do v - 1 . Są to rozsądne wymagania. vv1
András Salamon,
1
@ AndrásSalamon: dobrze! Naprawiając kodowanie i model (taśma odczytu jednokierunkowego + taśma robocza dwukierunkowa) otrzymujemy najgorszy czas działania na wejściach o rozmiarze n , gdzie c może być dowolnie duże, osadzając pewną stałą pamięć w wewnętrznej logice TM . Interesujące może być zbadanie, czy coś można udowodnić za pomocą jednostronności taśmy wejściowej i argumentu przekroju. 2ncnc
Marzio De Biasi,
1
Tak, o ile mogę powiedzieć, iloczyn czasoprzestrzenny dla Unary SAT to coś w rodzaju standardowym argumentem. Jednoargumentowa reprezentacja zmiennych pozwala uniknąć przerwy między najlepiej znanądolną granicąΩ(n2/(logn) 1 + ε )a bezpośredniągórną granicąO(n3/(logn) ε )dla CNF-SAT (chociaż lepszy algorytm w takim przypadku może również zmniejszyć różnicę). Θ(nn)Ω(n2/(logn)1+ε)O(n3/(logn)ε)
András Salamon,
2

Nie do końca to, czego szukasz, ale w przypadku NTM z 1 taśmą odpowiedź wydaje się być przecząca: SAT nie jest rozwiązywalny z NTM z 1 taśmą w niedeterministycznym czasie liniowym.

Zgodnie z tym artykułem (Twierdzenie 4.1), klasa języków regularnych jest dokładnie klasą języków rozpoznawanych przez 1-taśmowy NTM w czasie o ( n log ( n ) ) . Zatem jeśli istniałby 1-taśmowy NTM rozwiązujący SAT w czasie o ( n log ( n ) ) , to SAT (a dokładniej zbiór zadowalających wzorów w CNF) byłby językiem regularnym, a zatem rozwiązalnym w deterministycznej stałej przestrzeni.REG o(nlog(n))o(nlog(n))

Boson
źródło
5
Twierdzenie, że jest tylko o jednym głowy maszyn Turinga.(Na przykład dwugłowicowe maszyny Turinga mogą łatwo decydować o języku palindromu w czasie liniowym i stałej przestrzeni).
To jest świetne! Dziękuję Ci bardzo. Ale najbardziej interesuje mnie sprawa dwóch taśm. :)
Michael Wehar
2
Jak napisał @Ricky. AFAIK nadal jest zgodny z tym, co wiemy, że SAT jest w deterministycznym czasie liniowym. Aby udowodnić inaczej, potrzebna byłaby dolna granica czasu superlinearnego dla SAT, a my jej nie mamy (wydaje się, że nie jest blisko jednego).
Kaveh