Dlaczego 2SAT w P?

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

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⇒ b a b 2 l 1 ∨ l 2 Ź l 1 ⇒ l 2 Ź l 2 ⇒ l 1 b b a 1 Ź l l l Kontakty l $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.a ⇒ b ∨ c a b c a b $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.2 2 3 k - 1 $3$$2$$2$$3$$k-1$$k$

$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.

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 )

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.