Dlaczego 2SAT w P?

55

Natknąłem się na algorytm wielomianowy, który rozwiązuje 2SAT. Uważam za zaskakujące, że 2SAT znajduje się w P, gdzie wszystkie (lub wiele innych) instancji SAT są NP-Complete. Co wyróżnia ten problem? Co sprawia, że jest to takie proste (NL-Complete - nawet łatwiejsze niż P)?

— Chłopak
źródło

18

Dlaczego ludzie myślą, że to takie złe pytanie?

— Peter Shor

12

Ciekawym aspektem jest to, że jeśli chcesz poznać maksymalną liczbę klauzul spełniających wymagania jednocześnie w wyrażeniu 2SAT (tj. Max2SAT), to wrócisz do NP-complete.

— Shaun Harker,

11

Jest to albo okropne pytanie, ponieważ nie ma użytecznej odpowiedzi, albo fantastyczne pytanie, ponieważ jedyną prawidłową odpowiedzią jest „nikt nie wie”.

— Jeffε

12

Proszę przeczytać artykuł „Złożoność problemów satysfakcji: udoskonalenie twierdzenia Schaefera”.

— Diego de Estrada,

3

Drogi Człowieku, fakt, że 2SAT jest w P, jest omawiany w prawie każdym standardowym podręczniku złożoności, więc kiedy powiesz, że właśnie zauważyłeś, ten fakt sprawia, że pytanie wygląda tak, jakbyś nawet nie przeczytał standardowego podręcznika o złożoności.

— Kaveh

88

Oto kolejne intuicyjne i bezpretensjonalne wyjaśnienie zgodne z odpowiedzią MGwynne.

Z -sat można wyrazić tylko implikacje postaci , gdzie i są literały. Dokładniej, każda klauzula może być rozumiana jako para implikacji: i . Jeśli ustawisz na true, musi być prawdziwe. Jeśli ustawisz na false, musi być false. Takie implikacje są proste: nie ma wyboru, masz tylko $2$ $a \Rightarrow b$ $a$ $b$ $2$ $l_1 \lor l_2$ $\lnot l_1 \Rightarrow l_2$ $\lnot l_2 \Rightarrow l_1$ $a$ $b$ $b$ $a$ $1$ możliwość, nie ma miejsca na pomnożenie wielkości liter. Można po prostu śledzić każdą możliwą łańcuch domniemanie, i zobacz, czy kiedykolwiek czerpać zarówno z i z : jeśli nie jakiegoś , wówczas formuła 2-SAT jest unsatisfiable, w przeciwnym razie jest spe. Jest tak, że liczba możliwych łańcuchów implikacji jest wielomianowo ograniczona wielkością formuły wejściowej. $\lnot l$ $l$ $l$ $\lnot l$ $l$

Za pomocą SAT możesz wyrazić implikacje postaci , gdzie , i są literałami. Teraz masz kłopoty: jeśli ustawisz na true, to albo lub musi być prawdziwe, ale który? Musisz dokonać wyboru: masz 2 możliwości. W tym przypadku możliwe staje się mnożenie przypadków i powstaje wybuch kombinatoryczny. $3$ $a \Rightarrow b \lor c$ $a$ $b$ $c$ $a$ $b$ $c$

Innymi słowy, SAT jest w stanie wyrazić obecność więcej niż jednej możliwości, podczas gdy -SAT nie ma takiej zdolności. To właśnie taka obecność więcej niż jednej możliwości ( możliwości w przypadku SAT, możliwości w przypadku SAT) powoduje typową kombinatoryczną eksplozję problemów NP-zupełnych. $3$ $2$ $2$ $3$ $k-1$ $k$

— Giorgio Camerani
źródło

6

Chciałbym móc to jeszcze bardziej głosować! O wiele lepsza odpowiedź!

— MGwynne

5

@MGwynne: Dziękuję za bardzo miły komentarz. Nie ma za co, a twoja odpowiedź jest naprawdę bardzo dobra!

— Giorgio Camerani

8

To miła odpowiedź na dobre pytanie (IMHO). Jak napisał Mac Lane: „Matematycy wprowadzają skuteczne lub podchwytliwe formalne manipulacje, które bez wątpienia mają przewodnią ideę - ale łatwiej jest wyrazić te manipulacje niż sformułować ten pomysł słowami ... Perspektywiczne przedstawienie dzieła matematyki pozwala świecić ideom poprzez manipulacje ”. To konkretne pytanie i odpowiedź pomogło „prześwitywać pomysły” (dla mnie). Dzięki! :)

— John Sidles

4

@John: Nie ma za co! ;-) Bardzo dziękuję za twój wspaniały i hojny komentarz, naprawdę to doceniam. Nie mogłem się bardziej zgodzić ze słowami Mac Lane.

— Giorgio Camerani

Zgodnie z odpowiedzią Giorgio Camerani nie warto obniżać żadnego problemu NP do 3SAT, jeśli wprowadzisz więcej fałszywych zmiennych boolowskich, będziesz mieć więcej klauzul i nie będziesz mieć ani zysku, ani zysku, ale bardziej preferowane jest zmniejszenie go do CNF SAT lub satysfakcji boolowskiej lub Obwód SAT zamiast tego, ponieważ w tych problemach masz mniej zmiennych boolowskich i mniejszych klauzul, a to oznacza, że naiwne algorytmy brutalnej siły, mapy karnaugh i algorytm Quine-McClusky mają większą złożoność: D.

— Wymiana

31

$n + m -2 \le 2$ $n, m \le 2$ $n$ $m$

Po przejściu do 3-SAT możesz dostać coraz większe rezolwenty, więc wszystko idzie w kształcie gruszki :).

Spróbuj przetłumaczyć problem na 2-SAT. Ponieważ nie możesz mieć klauzul o rozmiarze 3, nie możesz (ogólnie) zakodować implikacji obejmujących 3 lub więcej zmiennych, na przykład, że jedna zmienna jest wynikiem operacji binarnej na dwóch innych. To jest ogromne ograniczenie.

— MGwynne
źródło

3

„Nie można zakodować takich rzeczy, jak implikacja” - IMP-SAT jest również w P (i myślę, że NL)

— Max

8

p \to q

$p \to q$

\neg p \lor q

$\lnot p \lor q$

1

Kaveh, dobry punkt, naprawiony teraz.

— MGwynne

Jak już powiedziałem, kiedy zredukujesz swój arbitralny problem NP do Boolean Satisfiable lub Circuit SAT lub CNF SAT, nie redukuj problemu do 3SAT, ponieważ problem staje się jeszcze trudniejszy i bardziej złożony z większą liczbą zmiennych boolowskich i klauzul. Nawet algorytm rozdzielczości staje się mniej wydajny w nowym problemie!

— Farewell Stack Exchange

20

Jak mówi Walter, klauzule 2-SAT mają specjalną formę. Można to wykorzystać, aby szybko znaleźć rozwiązania.

W rzeczywistości istnieje kilka klas instancji SAT, o których można decydować w czasie wielomianowym, a 2-SAT jest tylko jedną z tych klas możliwych do przełożenia . Istnieją trzy szerokie rodzaje przyczyn podatności na rozciąganie:

(Strukturalna podatność) Dowolną klasę instancji SAT, w których zmienne oddziałują w sposób podobny do drzewa, można rozwiązać w czasie wielomianowym. Stopień wielomianu zależy od maksymalnej szerokości instancji w klasie, gdzie szerokość mierzy, jak daleko instancja jest od drzewa. Dokładniej, Marks wykazał, że jeśli instancje ograniczyły szerokość podmodularną, wówczas o klasie można decydować w czasie wielomianowym, stosując podejście dziel i rządź.
(Zdolność językowa) Dowolną klasę instancji SAT, w których wzór zmiennych prawda-fałsz jest „ładny”, można rozwiązać w czasie wielomianowym. Dokładniej, wzór literałów określa język relacji, a Schaefer sklasyfikował sześć języków, które prowadzą do łatwości obsługi, każdy z własnym algorytmem. 2-SAT stanowi jedną z sześciu klas Schaefera.
(Możliwość hybrydyzacji) Istnieje również kilka klas instancji, które nie należą do pozostałych dwóch kategorii, ale które można rozwiązać w czasie wielomianowym z innych powodów.
- Dániel Marx, Tractable hypergraph właściwości dla ograniczenia satysfakcji i spójnych zapytań , STOC 2010. ( doi , preprint )
- Thomas J. Schaefer, Złożoność problemów satysfakcji , STOC 1978. ( doi )

— András Salamon
źródło

2

Istnieją również argumenty oparte na strukturze przestrzeni rozwiązania z losowej literatury k-SAT, które można wykorzystać do wyjaśnienia różnicy.

— Kaveh

3

@Kaveh: mój opis podatności na hybrydy miał być na tyle niejasny, by objąć takie rzeczy. Na przykład w bardzo szczególnych przypadkach można argumentować za satysfakcją w oparciu o lokalną lemat Lovásza. Zobacz ankietę Pearson and Jeavons z 1997 r .: cs.ox.ac.uk/publications/publication1610-abstract.html

— András Salamon

3

Należy również zauważyć, że SAT jest szczególnym przypadkiem problemu spełnienia ograniczenia, w którym każda zmienna może przyjmować 2 wartości. Gdy zmienne mogą przyjmować 3 wartości, istnieje 10 możliwych do opanowania klas językowych, sklasyfikowanych przez Andrieja Bułatowa : cs.sfu.ca/~abulatov/papers/3-el-journal.ps Klasy hybrydowe są również bardziej interesujące dla większych domen.

— András Salamon

10

Jeśli rozumiesz algorytm dla 2SAT, wiesz już, dlaczego jest on w P - właśnie to pokazuje algorytm. Myślę, że ten komiks ilustruje mój punkt widzenia. Jak już wiesz, dlaczego 2SAT jest w P, prawdopodobnie chcesz wiedzieć, dlaczego 2SAT nie jest NP-trudny.

Aby zrozumieć, dlaczego 2SAT nie jest trudny do NP, musisz zastanowić się, jak łatwo jest zredukować inne problemy z NP. Aby uzyskać intuicyjne zrozumienie tego, zobacz, jak SAT można zredukować do 3SAT i spróbuj zastosować te same techniki, aby zredukować SAT do 2SAT. 2SAT nie jest tak ekspresyjny jak 3SAT i inne warianty SAT.

— Dave
źródło