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

Odpowiedzi:

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 tylkob a b 2 l 1l 2 Ź l 1l 2 Ź l 2l 1 b b a 1 Ź l l l Kontakty l l2abab2l1l2¬l1l2¬l2l1abba1moż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.¬lll¬ll

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.a b c a b c a b c3abcabcabc

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.2 2 3 k - 1 k3223k1k

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+m22n,m2nm

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
pq¬pq
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:

  1. (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ź.

  2. (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.

  3. (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