Algorytmy i struktury danych/NP-zupełność

Ten wykład poświęcimy klasie bardzo użytecznych problemów, dla których nieznane są algorytmy wielomianowe i nie wiadomo, czy takie algorytmy w ogóle istnieją. Rozpoczniemy od podania algorytmu rozwiązującego następujące zadanie:

Dane: Formuła boolowska $\varphi$ w postaci koniunkcji zmiennych lub ich negacji.

Pytanie: Czy formuła $\varphi$ jest spełnialna, tzn. czy istnieje takie wartościowanie zmiennych, dla którego formuła $\varphi$ przyjmuje wartość 1 (Prawda)?

Przykład: Formuła $x_1\wedge \mathrm{\neg }{x}_2\wedge x_3\wedge x_1$ przyjmuje wartość 1 tylko dla wartościowania $x_1=1,x_2=0,x_3=1$.

Łatwo zauważyć, że formuła $\varphi$ (w postaci z powyższego zadania) jest spełnialna wtedy i tylko wtedy, gdy nie występują w niej jednocześnie zmienna i jej negacja. Ta obserwacja pozwala sformułować bardzo prosty algorytm rozwiązujący nasze zadanie:

1  Dla każdej zmiennej $x$ z $\varphi$ sprawdź, czy w $\varphi$ występują jednocześnie $x$ i $\mathrm{\neg }x$. 
2  Jeśli taka zmienna nie istnieje, to $\varphi$ jest spełnialna, w  
3  przeciwnym razie $\varphi$ nie jest spełnialna.
 

Sprawny programista bardzo szybo zaprogramuje powyższy algorytm. Musimy tylko sprecyzować, co oznacza sformułowanie dana jest formuła boolowska. Innymi słowy musimy podać rozsądny sposób kodowania formuł. Jednym z możliwych może być następujący sposób kodowania: Przyjmujemy, że zmienne występujące w formule są ponumerowane kolejno 1,2,$\dots$ Formułę kodujemy jako ciąg liczb poddzielonych średnikami. Pierwszą liczbą w ciągu jest liczba $n$ równa liczbie literałów, czyli wystąpień w formule zmiennych lub ich negacji. W formule z przykładu mamy cztery literały. Po liczbie literałów występuje $n$ liczb ze zbioru $\{-n,-(n-1),\dots ,-1,1,2,\dots ,n\}$. Jeśli $i$-tym literałem jest zmienna $x_k$, to za $i$-tą spośród tych liczb bierzemy $k$, jeśli zaś $i$-tym literałem jest $\mathrm{\neg }{x}_k$, to $i$-tą liczbą będzie $-k$.

Kodem przykładowej formuły jest $4;1;-2;3;1$

W każdym rozsądnym kodowaniu przyjmuje się ponadto, że do kodowania liczb stosujemy dowolny zapis o podstawie co najmniej 2 (najczęściej właśnie o podstawie 2). Zauważmy, że przy takim kodowaniu długość kodu formuły wynosi co najwyżej $cn\log n$, dla pewnej stałej $c$. Długość kodu danych będziemy nazywali rozmiarem zadania. W przedstawionym powyżej algorytmie literały są porównywane między sobą. Nawet przy bardzo naiwnej implementacji tego algorytmu liczba takich porównań wyniesie co najwyżej $n^2$. Jeśli uwzględnimy, że porównywanie kodów dwóch literałów wymaga $\log n$ porównań bitów, to liczbę wszystkich operacji da się ograniczyć przez $n^2\log n$, a idąc dalej możemy powiedzieć, że liczbę operacji wykonywanych przez algorytm da się ograniczyć przez $r^k$, gdzie $r$ jest rozmiarem danych, a $k$ stałą całkowitą większą od 0. (W naszym przypadku za $k$ można wziąć 3.) W takim przypadku mówimy, że algorytm rozwiązuje zadanie w czasie wielomianowym.

Klasą P nazywamy zbiór tych zadań algorytmicznych, dla których istnieją algorytmy rozwiązujące je w czasie wielomianowym.

Utrudnijmy teraz nasze wyjściowe zadanie.

Powiemy, że formuła boolowska jest w postaci koniunkcyjno-normalnej (z ang. w postaci CNF), jeśli jest koniunkcją formuł (klauzul), z których każda jest alternatywą zmiennych lub ich negacji, być może zdegenerowaną do jednego literału. Formuła jest w postaci $k$-CNF, jeśli w każdej klauzuli występuje co najwyżej $k$ literałów.

Ćwiczenie 1

Pokaż, że każdą formułę boolowską można przekształcić do równoważnej (ze względu na spełnialność) formuły w postaci 3-CNF o długości tylko wielomianowo większej od długości formuły wyjściowej.

Oto przykład formuły w postaci 2-CNF: $(x_1\vee \mathrm{\neg }{x}_2)\wedge (\mathrm{\neg }{x}_1\vee x_3)\wedge (\mathrm{\neg }{x}_2\vee \mathrm{\neg }{x}_3)$.}

Pokazaliśmy, że zadanie spełnialności formuł w postaci 1-CNF można rozwiązać w czasie wielomianowym. To stwierdzenie pozostaje w mocy także dla formuł w postaci 2-CNF.

Ćwiczenie 2

Zaprojektuj algorytm, który rozwiązuje to zadanie w czasie liniowym, tj. w czasie proporcjonalnym do długości formuły.

Sytuacja zmienia się diametralnie, gdy weźmiemy $k\ge 3$. Nie są znane algorytmy, które rozwiązywałyby to zadanie w czasie wielomianowym, nawet dla wielomianów bardzo dużego stopnia, np. 1000. Najlepsze znane algorytmy wymagają czasu co najmniej $c^r$, gdzie $c$ jest stałą większą od 1, a $r$ jest długością kodu formuły. O takich algorytmach mówimy, że działają w czasie wykładniczym. Z praktycznego punktu widzenia oznacza to, że nawet na współczesnych komputerach takie algorytmy mają szanse dać wynik w rozsądnym czasie tylko dla danych o bardzo małych rozmiarach. Można zaryzykować stwierdzenie, że jeżeli dla zadania algorytmicznego znamy tylko rozwiązania działające w czasie wykładniczym, to zadanie to jest praktycznie algorytmicznie nierozwiązywalne.

Jaką interesującą własność ma jeszcze zadanie spełnialności formuł boolowskich? Gdyby ktoś chciał przekonać nas, że dana formuła jest spełnialna wystarczy, żeby podał odpowiednie wartościowanie zmiennych. Zauważmy, że rozmiar takiego wartościowania nie jest większy od długości formuły. Mając takie wartościowanie, w czasie wielomianowym można obliczyć odpowiadającą mu wartość logiczną formuły. Jeśli tą wartością jest 1 (Prawda), to formuła jest spełnialna. Wartościowanie, dla którego formuła jest spełnialna nazywamy świadectwem spełnialności. Algorytm, który sprawdza spełnialność formuły dla danego wartościowania nazywamy algorytmem weryfikacji. Innymi słowy, algorytmu weryfikacji można użyć do wykazania w czasie wielomianowym, że dana formuła jest spełnialna, jeżeli tylko istnieje i dane jest odpowiednie świadectwo.

Klasą NP nazywamy zbiór tych zadań algorytmicznych, które można weryfikować w czasie wielomianowym. Skróty P i NP. pochodzą z angielskiego, odpowiednio, polynomial time i nondeterministic polynomial time. Niedeterminizm dotyczy pochodzenia świadectwa, ponieważ nie żąda się podania metody jego konstrukcji.

Łatwo zauważyć, że każde zadanie z P należy do NP, ponieważ zadanie takie można zawsze rozwiązać w czasie wielomianowym i do weryfikacji nie potrzebujemy żadnego świadectwa. Zatem $P\subseteq NP$, a problem P=NP, to problem

Czy $P\ne NP$?

Do klasy NP należą tysiące ważnych, praktycznych zadań algorytmicznych, o których nie wiadomo, czy należą do P. Przyjrzyjmy się jeszcze jednemu takiemu zadaniu.

Dane: Nieskierowany graf $G=(V,E)$ oraz liczba naturalna $k$.

Pytanie: Czy w $G$ istnieje klika rozmiaru $k$, tzn. czy w $G$ istnieje podgraf $k$-wierzchołkowy, w którym każda para różnych wierzchołków jest połączona krawędzią?

Problem kliki z pewnością należy do NP. Dla danego $k$-elementowego podzbioru wierzchołków (świadectwa) można łatwo w czasie wielomianowym, zależnym tylko od rozmiaru grafu, sprawdzić, czy wierzchołki te tworzą klikę. Pokażemy teraz, że gdybyśmy w czasie wielomianowym potrafili rozwiązać zadania spełnialności, to także w czasie wielomianowym można by rozwiązać zadanie kliki. W tym celu zadanie kliki sprowadzimy do zadania formuł boolowskich.

Dla każdego wierzchołka $v\in V$, wprowadzamy $k$ zmiennych boolowskich $x_1^v$, $x_2^v$,$\dots$, $x_k^v$. Zmienna $x_i^v$ intuicyjnie mówi, że wierzchołek $v$ jest $i$-tym wierzchołkiem w poszukiwanej klice. Skonstruujemy formułę $\varphi$, która jest koniunkcją trzech formuł ${\varphi }_1,{\varphi }_2$ i ${\varphi }_3$. Oto intuicyjne znaczenie i formalne definicje tych formuł:

• ${\varphi }_1=$ dla każdego $i$, $1\le i\le k$, istnieje co najmniej jeden wierzchołek $u\in V$, który jest $i$-tym wierzchołkiem w klice.
  • ${\varphi }_1=\underset{i=1}{\overset{k}{\bigwedge }}(\underset{v\in V}{\bigvee }{x}_i^v).$
• ${\varphi }_2=$ dla każdego $i$, $1\le i\le k$, żadne dwa wierzchołki nie są jednocześnie $i$-tymi wierzchołkami w klice.
  • ${\varphi }_2=\underset{i=1}{\overset{k}{\bigwedge }}\underset{u,v\in V,u\ne v}{\bigwedge }(\mathrm{\neg }{x}_i^u\vee \mathrm{\neg }{x}_i^v).$
• Dla każdej pary $u,v$, jeśli $u$-$v$ nie jest krawędzią w grafie, to $u$ i $v$ nie są jednocześnie w klice.
  • ${\varphi }_3=\underset{u\text{--}v\in ̸E}{\bigwedge }\underset{1\le i,j\le k}{\bigwedge }(\mathrm{\neg }{x}_i^u\vee \mathrm{\neg }{x}_j^v).$

Pozostawiamy czytelnikowi wykazanie, że formuła $\varphi$ jest spełnialna wtedy i tylko wtedy, gdy w grafie $G$ istnieje klika rozmiaru $k$. Łatwo zauważyć, że rozmiar powstałej formuły jest wielomianowo zależny od rozmiaru grafu, a samą formułę można skonstruować w czasie wielomianowym. W tym przypadku mówimy, że zadanie kliki jest redukowalne w czasie wielomianowym do zadania spełnialności. W 1971 roku R. Cook udowodnił, że każde zadanie z NP można w czasie wielomianowym zredukować do zadania spełnialności pewnej formuły boolowskiej. Zadanie, które należy do klasy NP i do którego można zredukować w czasie wielomianowym każde inne zadanie z NP nazywamy zadaniem NP-zupełnym. W tym sensie zadanie spełnialności jest NP-zupełne. Pozostawiamy czytelnikom pokazanie, że zadanie kliki jest też NP-zupełne. W tym celu wystarczy pokazać wielomianową redukcję zadania spełnialności do zadania kliki. Rozwiązanie dowolnego zadania NP-zupełnego w czasie wielomianowym pozwalałoby rozwiązywać w czasie wielomianowym każde zadanie z NP.

Pojęcie klasy P wprowadzili niezależnie Cobham i Edmonds w połowie lat sześćdziesiątych. Edmonds wprowadził też pojęcie klasy NP i jako pierwszy sformułował pytanie, czy P $\ne$ NP. Metoda redukcji pochodzi od Karpa, który przy jej pomocy pokazał, że wiele ważnych zadań kombinatorycznych jest NP-zupełnych.