Dwie zmienne w klauzuli są łatwe, trzy wystarczą do NP-zupełności
2-SAT i 3-SAT wyglądają niemal identycznie: w obu szukamy wartości prawda/fałsz dla zmiennych tak, aby spełnić formułę logiczną w postaci koniunkcji klauzul. Różnica polega na maksymalnej liczbie literałów w klauzuli. Dla 2-SAT istnieje algorytm liniowy oparty na grafie implikacji i silnie spójnych składowych. 3-SAT jest natomiast jednym z klasycznych problemów NP-zupełnych. To niezwykły przykład „progu złożoności”: pozornie drobne rozszerzenie lokalnego warunku z dwóch do trzech literałów wystarcza, by przejść od problemu efektywnie rozwiązywalnego do problemu reprezentującego pełną trudność NP.
Co właściwie ograniczamy
Formuła w postaci CNF jest koniunkcją klauzul, a każda klauzula jest alternatywą literałów, czyli zmiennych lub ich negacji. W 2-SAT każda klauzula zawiera najwyżej dwa literały, np. (x ∨ ¬y). W 3-SAT dopuszczamy klauzule z trzema literałami. Zadanie brzmi: czy istnieje takie przypisanie wartości logicznych wszystkim zmiennym, aby cała formuła była prawdziwa? Różnica w zapisie jest niewielka, ale struktura algorytmiczna zmienia się bardzo mocno.
Dlaczego 2-SAT daje się sprowadzić do grafu
Klauzulę (a ∨ b) można zapisać jako dwie implikacje: ¬a → b oraz ¬b → a. Z całej formuły buduje się graf implikacji, którego wierzchołkami są literały. Kluczowe kryterium mówi, że formuła 2-SAT jest niespełnialna wtedy, gdy pewna zmienna i jej negacja trafiają do tej samej silnie spójnej składowej. Aspvall, Plass i Tarjan pokazali algorytm działający liniowo względem rozmiaru tak skonstruowanej reprezentacji. Zamiast przeglądać wszystkie 2^n przypisań, rozwiązujemy dobrze znany problem grafowy.
Trzeci literał łamie prostą strukturę
W klauzuli z trzema literałami nie da się zachować całej informacji za pomocą prostych implikacji parami w taki sposób, jak w 2-SAT. 3-SAT należy do klasycznych problemów NP-zupełnych. Oznacza to, że każdy problem z NP można wielomianowo do niego zredukować. Nie jest to dowód, że 3-SAT wymaga czasu wykładniczego — to zależałoby od rozwiązania P vs NP — ale znamy fundamentalną różnicę klasyfikacyjną między 2-SAT i 3-SAT.
To nie magia liczby trzy
Nie należy wyciągać wniosku, że „trzy zawsze jest trudne, dwa zawsze łatwe”. Próg zależy od struktury konkretnej rodziny problemów. Siła przykładu polega na tym, że dwa prawie identycznie opisane warianty tego samego zadania logicznego lądują po przeciwnych stronach bardzo ważnej granicy: jeden w P, drugi NP-zupełny. Pokazuje to, jak ostro złożoność może reagować na niewielką zmianę reguł.
Praktyczny paradoks SAT
SAT i jego odmiany są jednocześnie centralnymi przykładami teorii trudności i niezwykle ważnymi problemami praktycznymi. Nowoczesne solvery potrafią rozwiązywać ogromne, dobrze ustrukturyzowane instancje. Teoria najgorszego przypadku nie zaprzecza temu sukcesowi. Mówi tylko, że klasa dopuszczalnych instancji 3-SAT jest na tyle bogata, by zakodować wszystkie problemy w NP.
Granica dotyczy ogólnego problemu, nie każdej formuły
NP-zupełność 3-SAT nie oznacza, że każda formuła z trzema literałami w klauzuli jest trudna. Wiele instancji może być banalnych: część upraszcza się natychmiast, część ma oczywiste przypisanie, a nowoczesne solvery wykorzystują liczne regularności. Klasyfikacja mówi o rodzinie wszystkich wejść i o najgorszym zachowaniu potrzebnym do rozwiązania problemu w pełnej ogólności. Podobnie 2-SAT nie jest „łatwy dlatego, że ma mało zmiennych”; może zawierać ich miliony, ale zachowuje szczególną strukturę implikacyjną. To właśnie struktura, a nie sama wielkość zapisu, stanowi sedno kontrastu między 2-SAT a 3-SAT.
Dlaczego kontrast 2-SAT/3-SAT jest tak pouczający
Ten przykład uczy ostrożności przy formułowaniu ograniczeń. „Najwyżej dwa” i „najwyżej trzy” wyglądają jak kosmetyczna zmiana parametru, ale pierwsza wersja pozwala przejść do grafu implikacji, a druga potrafi zakodować dowolny problem z NP poprzez redukcję. W analizie algorytmów warto więc szukać nie tylko wielkości wejścia, lecz także progów strukturalnych, po których znika własność wykorzystywana przez szybki algorytm.