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 .
Pytanie: Czy istnieje NTM, który rozwiązuje CNF-SAT w krokach ?
Wszelkie odnośne referencje są doceniane, nawet jeśli zapewniają jedynie niedeterministyczne podejścia zbliżone do liniowego.
time-complexity
sat
turing-machines
np
nondeterminism
Michael Wehar
źródło
źródło
Odpowiedzi:
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∨ ¬ xjot∨ xk) φ n m Σ={+,−,1}
Na przykład można przekonwertować na:(x2∨−x3∨+4)
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 ∈φi U(φi) jest NP-kompletny.LU={U(φi)∣φi∈3−SAT}
NTM z 2 taśmami może zdecydować, czy ciąg w czasie 2 | x | w ten sposób.x∈LU 2|x|
Przykład:
Czas można skrócić do jeśli dodamy kilka zbędnych symboli do reprezentacji klauzuli:|x|
( 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ę.
źródło
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))
źródło