Złożoność obliczeniowa/Wykałd 4: Redukcje i zupełność

Redukcje i zupełność

W poprzednim module przedstawione zostały podstawowe klasy złożoności dla problemów, jak również zależności między nimi. W tym rozdziale poznamy narzędzie bardzo pomocne przy określaniu przynależności problemów do zadanej klasy złożoności - redukcje.

Redukcje

Definicja

Niech ${ℱ}$ będzie pewną rodziną funkcji o sygnaturze

 $\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$

domkniętą na składanie i zawierającą identyczność. Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$ (czyli inaczej mówiąc zakodowanymi binarnie problemami decyzyjnymi). Mówimy, że problem $L_1$ jest redukowalny do problemu $L_2$ w sensie rodziny ${ℱ}$ i zapisujemy

 $L_1{\le }_{{ℱ}}{L}_2$

wtedy i tylko wtedy, gdy

 ${\mathrm{\exists }}_{f\in {ℱ}}{\mathrm{\forall }}_{w\in \{0,1{\}}^{\star }}w\in L_1⟺f(w)\in L_2$

Intuicyjnie problem $L_1$ jest w pewnym sensie co najwyżej tak trudny jak problem $L_2$ - jeżeli znamy rozwiązanie problemu $L_2$ oraz odpowiednią funkcję (zwaną redukcją lub transformacją), to znamy również rozwiązanie problemu $L_1$. Warto zauważyć, że relacja ${\le }_{{ℱ}}$ jest preporządkiem, to znaczy jest zwrotna (ze względu na obecność identyczności) i przechodnia (ze względu na domkniętość rodziny ${ℱ}$ na składanie).

Przedstawmy teraz najczęściej stosowane rodziny redukcji.

Redukcje wielomianowe

Rodzina redukcji wielomianowych (Karpa) to rodzina funkcji $\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$ obliczalnych nadeterministycznej maszynie Turinga w czasie wielomianowym. Redukowalność w sensie rodziny redukcji wielomianowych najczęściej po prostu nazywa się redukowalnością wielomianową.

Klasycznym przykładem redukowalnosci wielomianowej jest redukowalność problemu maksymalnego skojarzenia w grafie dwudzielnym do problemu maksymalnego przepływu w grafie skierowanym.

ZO-4-1. Przekształcenie grafu dwudzielnego w sieć przepływową.

Redukcje wielomianowe mają ważną własność: Jeżeli problem $L_1$ jest redukowalny wielomianowo do problemu $L_2$ oraz $L_2$ należy do klasy $P$, to $L_1$ również należy do klasy $P$. Aby uzasadnić tą własność wystarczy skonstruować maszynę, która najpierw przekształci instancję problemu $L_1$ do instancji problemu $L_2$ (uczyni to w czasie wielomianowym, bo $L_1$ jest wielomianowo redukowalne do $L_2$), po czym w czasie wielomianowym da odpowiedź dla instancji problemu $L_2$.

Ćwiczenie 1

Załóżmy, że $L_1$ jest wielomianowo redukowalne do $L_2$ oraz $L_2$ należy do klasy $NP$. Pokaż, że $L_1$ również należy do klasy $NP$.

Rozwiązanie

Należy tutaj skorzystać z faktu, że deterministyczna maszyna Turinga jest specjalnym przypadkiem maszyny niedeterministycznej. Wystarczy zatem najpierw uruchomić deterministyczną maszynę implementującą redukcję z $L_1$ do $L_2$, po czym uruchomić niedeterministyczną maszynę, rozwiązującą problem $L_2$ w czasie wielomianowym. Otrzymamy w tym momencie niedeterministyczną maszynę rozwiązującą problem $L_1$. Należy jeszcze tylko uzasadnić, czemu łączny czas działania tej maszyny będzie wielomianowo zależny od wielkości wejścia; wiemy jednak, że wyjście redukcji jest co najwyżej wielomianowo zależne

od wielkości wejścia (maszyna "nie ma czasu" żeby zapisać więcej komórek), oraz że złożenie dwóch wielomianów daje w efekcie wielomian. Własności te sprawiają, że ostateczny program będzie miał wielomianową złożoność, a co za tym idzie problem $L_1$ będzie należał do klasy $NP$.

Redukcje logarytmiczne

Drugą ciekawą rodziną redukcji jest rodzina redukcji logarytmicznych. Aby zdefiniować tą rodzinę zmodyfikujemy definicję maszyny Turinga - otóż wyznaczamy na niej dwie specjalne taśmy - wejściową (tylko do odczytu, tak jak przy maszynie off-line) i wyjściową. Po zapisie na taśmę wyjściową głowica przesuwa się zawsze w tym samym kierunku, co uniemożliwia odczyt poprzednio zapisanych symboli.

Powróćmy teraz do redukcji. Redukcja logarytmiczna jest funkcją obliczalną na deterministycznej maszynie Turinga z użyciem logarytmicznej ilości pamięci na taśmie roboczej. Zauważmy, że nie nakładamy żadnych ograniczeń na wielkość słowa wyjściowego - najczęśniej jego wielkość będzie wielomianowo zależna od wielkości słowa wejściowego. Intuicyjnie transformacja logarytmiczna pozwala przechowywać na taśmie roboczej stałą liczbę wskaźników do komórek wejściowych (lub innych obiektów o podobnej wielkości).

Ćwiczenie 2

Czy problem maksymalnego skojarzenia w grafie dwudzielnym jest redukowalny do problemu maksymalnego przepływu w sensie rodziny transformacji logarytmicznych?

Wskazówka

Prześledź, jakie dane muszą się znajdować w pamięci (czyli na taśmie roboczej) maszyny Turinga, wykonującej transformację.

Rozwiązanie

Załóżmy, że graf dwudzielny jest przedstawiony w postaci macierzy sąsiedztwa (niekoniecznie kwadratowej - w końcu wiemy, że graf wejściowy jest dwudzielny), oraz że na wyjście chcemy również wypisać graf w postaci macierzy sąsiedztwa (tym razem już kwadratowej). Problem ten możemy rozwiązać używając następujących danych na taśmie tymczasowej:

• dwie liczby reprezentujące pozycję aktualnie wypisywanego elementu macierzy wyjściowej (każda o rozmiarze logarytmicznie zależnym od wielkości wejścia),

• liczbę pamiętającą aktualną pozycję głowicy na taśmie wejściowej (rozmiar j.w.).

Aby wypisać jakiś element macierzy wyjściowej musimy sprawdzić, jakiego typu są odpowiadające mu wierzchołki, czyli czy są one: źródłem, ujściem, elementem pierwszego zbioru czy elementem drugiego zbioru. Taka klasyfikacja może zostać wykonana z użyciem logarytmicznej ilości pamięci (polega ona na wykonaniu kilku porównań liczb o rozmiarze logarytmicznym). Jeżeli okaże się, że element macierzy reprezentuje krawędź pomiędzy rozłącznymi zbiorami grafu dwudzielnego, to będziemy musieli odwołać się do grafu wejściowego. W tym celu będziemy musieli obliczyć numer komórki na taśmie wejściowej, która reprezentuje interesującą nas krawędź; możemy to jednak zrobić z użyciem tylko takiej ilości pamięci, która jest potrzebna aby zapisać wynik. Pozostaje nam już tylko przesunąć się do odpowiedniej komórki - ta operacja nie wymaga już jednak żadnej dodatkowej pamięci.

Możemy zatem stwierdzić, że przedstawiona powyżej redukcja działa z użyciem logarytmicznej ilości pamięci; problem maksymalnego skojarzenia w grafie dwudzielnym jest zatem redukowalny do problemu maksymalnego przepływu w sensie redukcji logarytmicznej.

Ćwiczenie 3

Czy istnienie redukcji logarytmicznej z problemu $L_1$ do problemu $L_2$ implikuje istnienie redukcji wielomianowej z $L_1$ do $L_2$? Odpowiedź uzasadnij.

Wskazówka

Zastosuj podobne rozumowanie, jak przy porównywaniu klas $P$ i $L$.

Rozwiązanie

Można łatwo oszacować liczbę konfiguracji, w których znajduje się maszyna implementująca redukcję logarytmiczną; składa się na nią ilość pozycji, w których może się znajdować głowica taśmy wejściowej ($(O(n))$ - możemy bezpiecznie założyć, że maszyna nie przesuwa się "zbyt daleko poza wejście" na tej taśmie), liczba stanów oraz liczba różnych napisów, które mogą się znaleźć na taśmie roboczej ($2^{O(\log n)}=O(n^k)$, dla pewnej stałej $k$). Liczba konfiguracji tej maszyny jest zatem wielomianowo zależna od wielkości wejścia; czas działania maszyny implementującej redukcję (a zatem "niezapętlającej się") musi być więc co najwyżej wielomianowy w stosunku do wielkości wejścia.

Istnienie redukcji logarytmicznej pociąga zatem za sobą istnienie redukcji wielomianowej.

Warto się zastanowić czy prawdziwa jest następująca hipoteza:

Ta niewątpliwie cenna (o ile prawdziwa) hipoteza nie jest jednak tak oczywista jak poprzednio pokazywane analogiczne fakty dla transformacji wielomianowej i klas $P$ oraz $NP$. Problem przy "składaniu" dwóch maszyn - transformacji oraz maszyny rozwiązującej $L_2$ - tkwi w tym, że być może nie będziemy w stanie zapisac wyjścia transformacji (o potencjalnie wielomianowej wielkości) na taśmie roboczej.

Posłużymy się tutaj następującym trikiem: Uruchomimy maszynę rozwiązującą problem $L_2$; za każdym razem, gdy maszyna ta będzie chciała odwołać się do któregoś - dla ustalenia uwagi $i$-tego - bitu wejścia, na osobnej taśmie uruchomimy maszynę implementującą redukcję z $L_1$ do $L_2$. Maszyna ta nie będzie jednak wypisywać kolejnych symboli na wyjście, tylko inkrementować specjalnie utworzony licznik operacji wyjścia; w momencie, gdy wykonana zostanie $i$-ta operacja wyjścia, maszyna powróci do wykonywania programu rozwiązującego problem $L_2$, wykorzystująć symbol, który miał zostać wypisany na wyjście przez maszynę transformującą. Takie postępowanie wydaje się mało wydajne - tym niemniej na taśmach roboczych nigdy nie znajduje się większa niż logarytmiczna liczba symboli - a zatem otrzymujemy algorytm dla problemu $L_1$, wykorzystujący logarytmiczną ilośc symboli. Analogiczny argument można zastosować do pokazania, że rodzina transformacji logarytmicznych jest domknięta na składanie.

Transformacja wielomianowa w sensie Turinga

Definiowana tutaj transformacja będzie miała trochę inny charakter od dwóch poprzednich - w szczególności formalnie nie będzie ona redukcją. Do jej zdefiniowania będziemy potrzebować pojęcia maszyny z wyrocznią.

Definicja

Maszyna z wyrocznią $Q\subseteq \{0,1{\}}^{\star }$ jest wielotaśmową maszyną Turinga, z jedną wyróżnioną taśmą i trzema wyróżnionymi stanami $\{q_a,q_b,q_c\}$. Zachowanie maszyny różni się od zachowania zwykłej maszyny Turinga w następujący sposób: Przejście maszyny do stanu $q_a$ jest traktowane jako odwołanie do wyroczni $Q$. Jeżeli słowo aktualnie zapisane na wyróżnionej taśmie należy do języka $Q$, to maszyna przechodzi do stanu $q_b$; w przeciwnym razie przechodzi do stanu $q_c$. Odwołanie do wyroczni wliczane jest do czasu działania maszyny jako jedno przejście.

Mówiąc nieformalnie maszyna może w trakcie działania wielokrotnie prosić wyrocznię o rozwiązanie problemu $Q$.

Definicja

Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$. Mówimy, że $L_1$ transformuje się do $L_2$ w sensie wielomianowej transformacji Turinga wtedy i tylko wtedy gdy istnieje maszyna Turinga z wyrocznią $L_2$ rozwiązująca $L_1$ w czasie wielomianowym.

Transformacja Turinga intuicyjnie odpowiada stosowaniu podprogramów - jeżeli znamy rozwiązanie problemu $L_2$ to stosujemy go jako podprocedurę przy rozwiązywaniu problemu $L_1$.

Ćwiczenie 4

Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$ oraz niech $L_1$ transformuje się do $L_2$ w sensie transformacji wielomianowej Turinga. Które z poniższych zdań jest prawdziwe:

• $L_1\in P\Rightarrow L_2\in P$,

• $L_2\in P\Rightarrow L_1\in P$?

Rozwiązanie

Po pierwsze należy zauważyć, że transformacja z problemu $L_1$ do $L_2$ nie mówi nam absolutnie nic o złożoności problemu $L_2$. Dodatkowo jeśli $L_1\in P$ to problem ten transformuje się w sensie Turinga do każdego problemu decyzyjnego (czyli np. do problemu trywialnego, albo problemu podwójnie wykładniczego) - można rozwiązać ten problem w ogóle nie odwołując się do wyroczni.

Druga implikacja oczywiście zachodzi. Problem $L_1$ można rozwiązać stosując rozwiązanie problemu $L_2$ jako subrutynę. Złożoność czasowa tego rozwiązania będzie określona od góry przez złożenie dwóch wielomianów - co jak wiemy również jest wielomianem.

Niniejsze ćwiczenie ma za zadanie zaprezentowanie pewnego częstego błędu logicznego; zazwyczaj bowiem jeśli myślimy o subrutynie, to traktujemy ją jako coś prostszego od całego problemu. W tej sytuacji jednak -- gdy mamy wielomianowy (czyli "prosty") algorytm używający pewnej subrutyny -- widzimy, że jedyna trudność w rozwiązywaniu danego problemu może tkwić w "trudności" tej właśnie subrutyny.

Łatwo zauważyć, że transformacja wielomianowa w sensie Turinga wyznacza preporządek na językach zawartych w $\{0,1{\}}^{\star }$. Oznaczamy ją symbolem ${\le }_T$.

Ćwiczenie 5

Które z poniższych zdań jest prawdziwe:

• $L_1{\le }_T{L}_2\Rightarrow L_1{\le }_P{L}_2$,

• $L_1{\le }_P{L}_2\Rightarrow L_1{\le }_T{L}_2$?

Rozwiązanie

Udowodnienie prawdziwości drugiego zdania jest natychmiastowe - wystarczy na maszynie z wyrocznią wykonać redukcję wielomianową (w sensie Karpa), po czym odwołać się do wyroczni i w zależności od jej odpowiedzi przejść do stanu akceptującego lub odrzucającego.

Pierwsze zdanie nie jest prawdziwe; zauważyliśmy wcześniej, że problemy z $P$ są redukowalne w sensie Turinga do każdego problemu - w szczególności do problemu reprezentowanego przez język pusty. Łatwo zauważyć, że nietrywialnych - to znaczy nie reprezentowanych przez język pusty ani pełny - problemów z klasy $P$ nie da się zredukować w sensie transformacji wielomianowej Karpa do problemu reprezentowanego przez język pusty; maszyna akceptująca ten język nigdy nie da odpowiedzi 'tak'.

Widać, że powyższy dowód stosuje pewien "kruczek" w definicji redukcji; jeżeli założymy, że język $L_2$ nie może być pusty ani pełny, to prawdziwość pierwszego zdania będzie problemem otwartym.

Zupełność

Zastosujemy teraz zdefiniowane uprzednio rodziny transformacji do zdefiniowania dla wybranych klas złożoności ich najbardziej reprezentatywnych przedstawicieli - swoistej arystokracji w ramach danej klasy.

Definicja

Niech ${𝒞}$ będzie pewną klasą złożoności, natomiast $⊑$ preporządkiem określonym na językach zawartych w $\{0,1{\}}^{\star }$ (w domyśle jedną ze zdefiniowanych wcześniej rodzin transformacji). Mówimy, że problem decyzyjny $L\subseteq \{0,1{\}}^{\star }$ jest ${𝒞}$-zupełny w sensie preporządku $⊑$ wtedy i tylko wtedy, gdy:

• $L\in {𝒞}$,

• ${\mathrm{\forall }}_{L^{\prime }\in {𝒞}}{L}^{\prime }⊑L$.

Intuicyjnie problem ${𝒞}$-zupełny jest najtrudniejszym do rozwiązania problemem w klasie złożoności ${𝒞}$. Warto zauważyć, że może istnieć (i zazwyczaj istnieje) więcej niż jeden problem ${𝒞}$-zupełny. Problemy te są równoważne w sensie relacji preporządku $⊑$.

Ćwiczenie 6

Scharakteryzuj problemy $P$-zupełne w sensie transformacji wielomianowej.

Rozwiązanie

Problemami $P$-zupełnymi są wszystkie problemy reprezentowane przez nietrywialne (to znaczy nie-puste i nie-pełne) języki. Transformacja języka $L_1\in P$ do nietrywialnego języka $L_2\in P$ będzie tutaj polegała na rozwiązaniu problemu $L_1$, a następnie - w zależności czy obliczenie jest akceptujące czy nie - na wypisaniu jednej z dwóch ustalonych wcześniej instancji problemu $L_2$, z których pierwsza należy a druga nie należy do $L_2$.

Jak zauważyliśmy rozpatrywana powyżej klasa jest mało interesująca. Jeszcze mniej interesująca jest oczywiście klasa problemów $P$-zupełnych w sensie transformacji wielomianowej Turinga. Dla odróżnienia - klasa problemów $P$-zupełnych w sensie transformacji logarytmicznej cieszy się niemałym zainteresowanie specjalistów z dziedziny złożoności obliczeniowej; z tego powodu najczęściej określa się ją po prostu jako klasę problemów $P$-zupełnych.

Uwaga [na marginesie]

Przykładem problemu $P$-zupełnego jest problem HORNSAT. Jego opis można znaleźć w ...

Klasa NP i NP-zupełność

W ramach tego kursu naszym największym zainteresowaniem będzie się cieszyć klasa $NP$, a w szczególności problemy $NP$-zipełne w sensie trzech poznanych wcześniej rodzin transformacji. Zanim jednak przejdziemy do problemów $NP$-zupełnych, poznamy pewną alternatywną definicję klasy złożoności $NP$.

Twierdzenie

Niech $L\subseteq \{0,1{\}}^{\star }$. Wtedy:

$L\in NP⟺{\mathrm{\exists }}_{p(x)-wielomian}{\mathrm{\exists }}_{L^{\prime }\in P}{\mathrm{\forall }}_{n\in \mathbb{\mathbb{N}}}{\mathrm{\forall }}_{w\in \{0,1{\}}^n}[w\in L⟺({\mathrm{\exists }}_{v\in \{0,1{\}}^{p(n)}}⟨w,v⟩\in L^{\prime })]$

Zanim udowodnimy powyższy fakt, spróbujmy najpierw prześledzić, co się właściwie dzieje po prawej stronie równoważności. Słowo $v$ zwykle nazywane jest świadkiem (ang. witness) słowa $w$. Żądamy, żeby każde słowo należące do języka $L$ miało świadka o długości wielomianowej, natomiast żadne słowo spoza $L$ takiego świadka nie miało. Co więcej - żądamy, aby sprawdzanie, czy $v$ jest świadkiem słowa $w$ było wykonywane w czasie wielomianowym na maszynie deterministycznej - dlatego klasę $NP$ czasem nazywamy klasą problemów weryfikowalnych w czasie wielomianowym.

Przykład [$NONPRIME$]

Rozważmy problem $NONPRIME$. Niech $w\in \{0,1{\}}^{\star }$ będzie reprezentacją liczby naturalnej w systemie binarnym.

 $w\in NONPRIME⟺$ liczba reprezentowana przez $w$ nie jest liczbą pierwszą

Aby pokazać, że liczba nie jest pierwsza, wystarczy podać dowolny jej nietrywialny dzielnik (nie dotyczy to oczywiście liczby 1). Właśnie ten dzielnik będzie naszym świadkiem (w specjalnym przypadku liczby 1 uznamy, że jej świadkiem jest 1). Język $L^{\prime }$ będzie miał wtedy następującą postać:

 $L^{\prime }:=\{⟨w,v⟩:(num(v)\ne num(w)\wedge num(v)\ne 1\wedge num(v)\mid num(w))\vee num(w)=num(v)=1\}$

gdzie $num(v)$ oznacza liczbę reprezentowaną przez słowo $v$. Łatwo zauważyć, że $L^{\prime }$ jest implementowalna w czasie wielomianowym na deterministycznej maszynie - wystarczy pisemnie podzielić $w$ przez $v$, sprawdzić, czy zostanie reszta z dzielenia i ewentualnie obsłużyć przypadek brzegowy (liczbę 1). Zatem jak tylko udowodnimy powyższe twierdzenie, będziemy mogli stwierdzić, że $NONPRIME\in NP$.

Dowód

W stronę $\Leftarrow$ dowód jest prosty - skonstruujemy niedeterministyczną maszynę Turinga, rozwiązującą problem $L$. Maszyna ta najpierw przesunie głowicę za słowo wejściowe, przez następne $p(n)$ kroków będzie wypisywać na taśmę symbole 0 lub 1 (tu jest stosowany niedeterminizm) i przesuwać głowicę w prawo. Od tej pory maszyna będzie działać całkowicie deterministycznie - przesunie się na początek taśmy i zacznie się zachowywać jak deterministyczna maszyna rozwiązująca problem $L^{\prime }$ w czasie wielomianowym.

Jeżeli dla słowa wejściowego $w$ istnieje świadek, to zostanie on wygenerowany przez jedną ze ścieżek postępowania w etapie niedeterministycznym. W przeciwnym przypadku wszyscy "kandydaci na świadków" zostaną odrzuceni (zdemaskowani) przez maszynę rozwiązującą $L^{\prime }$.

Udowodnijmy teraz przejście w drugą stronę ($\Rightarrow$). Skoro $L\in NP$ to istnieje niedeterministyczna maszyna Turinga - $M$ - rozstrzygająca problem $L$. Niech $k$ oznacza maksymalny stopień rozgałęzienia maszyny $M$, tj.

 $k:=\underset{(s,q)\in \mathrm{\Sigma }\times Q}{\max }\mathrm{\#}d(s,q)$

czyli mówiąc nieformalnie największą liczbę rozgałęzień, która może się dokonać w jednym kroku. Łatwo zauważyć, że istnieje równoważna maszyna $M^{\prime }$ co najwyżej $k-1$-krotnie wolniejsza (a zatem nadal wielomianowa) o maksymalnym stopniu rozgałęzienia równym 2 - uzasadnienie przedstawione jest na poniższym rysunku.

[[ZO-4-2. Przekształcanie rozgałęzienia stopnia $k$ w $k-1$ rozgałęzień stopnia 2.]]

Od tej pory będziemy się zajmować maszyną $M^{\prime }$. Oznaczmy jej czas działania jako $W(n)$; w związku z tym maszyna dla słowa wielkości $n$ wykona co najwyżej $W(n)$ rozgałęzień. Każda ścieżka postępowania maszyny $M^{\prime }$ jest zatem zdefiniowana poprzez ciąg $W(n)$ bitów mówiących, którą spośród co najwyżej dwóch dostępnych ścieżek została wybrana. Jako "kandydatów na świadków" wybierzmy zatem ciągi $\{0,1{\}}^{W(n)}$, świadkiem natomiast niech będzie ciąg reprezentujący akceptującą ścieżkę postępowania maszyny $M^{\prime }$ - o ile taka istnieje.

Wystarczy w tym momencie wksazać deterministyczna maszynę Turinga $N$, rozpoznającą język $L^{\prime }$ - czyli weryfikującą dla pary słów $⟨w,v⟩$ czy $v$ jest świadkiem dla $w$. Maszyna taka jest prosta do skonstruowania w następujący sposób:

• $N$ najpierw przepisuje $v$ na tasmę pomocniczą, po czym wraca na głównej taśmie do początku słowa $w$,

• $N$ zachowuje się podobnie jak maszyna $M^{\prime }$; w przypadku, gdy maszyna ma do wyboru dwie opcje, $N$ sięga po kolejny dostępny bit taśmy pomocniczej i na jego podstawie wybiera ścieżkę postępowania.

Łatwo zauważyc, że $M^{\prime }$ akceptuje słowo $w$ wtedy i tylko wtedy gdy istnieje świadek, który spowoduje że maszyna $N$ dojdzie do stanu akceptującego.

Poznaliśmy zatem alternatywna definicję klasy $NP$. Potocznie często mówi się, że maszyna rozwiązująca problem z klasy $NP$ najpierw "zgaduje" świadka, a potem weryfikuje go w deterministyczny sposób w czasie wielomianowym. Należy jednak pamiętać, że maszyna w rzeczywistości nie "zgaduje" - zamiast tego sprawdza ona wszystkich możliwych świadków.

Powrócmy teraz do redukcji i problemów zupełnych. Oznaczmy jako $NPC$, $NP{C}_L$ i $NP{C}_T$ klasy problemów $NP$-zupełnych w sensie odpowiednio transformacji wielomianowej Karpa, transformacji logarytmicznej i transformacji wielomianowej Turinga. W tym momencie w żaden sposób nie uzasadniliśmy jeszcze, dlaczego którakolwiek z tych klas miałaby być niepusta. Mimo to już w tym momencie można okreslić pewne relacje zawierania pomiędzy tymi klasami.

Ćwiczenie 7

Uszereguj klasy $NPC$, $NP{C}_L$ i $NP{C}_T$ od najwęższej do najszerszej i uzasadnij to uszeregowanie.

Rozwiązanie

Prawdziwe są następujące zawierania:

 $NP{C}_L\subseteq NPC\subseteq NP{C}_T$

Weźmy dowolny problem z $NP{C}_L$. Wiemy, że można do niego przekształcić każdy problem z $NP$ z użyciem transformacji logarytmicznej. Na podstawie udowodnionych wcześniej faktów wiemy jednak, że redukowalność logarytmiczna implikuje redukowalność wielomianową; rozpatrywany problem należy zatem do klasy $NPC$. Analogiczne rozumowanie można zastosować do uzasadnienia drugiej inkluzji.

Nie wiadomo czy pomiędzy jakąś parą klas zachodzi równość.

Problem SAT

Zdefiniowanie problemu $SAT$ wymaga uprzedniego wprowadzenia (względnieprzypomnienia) kilku pojęć z dziedziny logiki:

• literałem nazywamy zmienną lub jej zaprzeczenie,

• klauzulą nazywamy alternatywę skończonej liczby literałów,

• mówimy, że formuła logiczna jest w koniunkcyjnej postaci normalnej wtedy i tylko wtedy gdy jest koniunkcją skończonej liczby klauzul. Przykładem formuły w koniunkcyjnej postaci normalnej jest formuła:

 $(x_1\vee x_2\vee \mathrm{\neg }{x}_3)\wedge (x_2\vee x_3)\wedge (\mathrm{\neg }{x}_1\vee \mathrm{\neg }{x}_4)$

Mówimy, że formuła jest spełnialna wtedy i tylko wtedy gdy istnieje wartościowanie zmiennych, dla których ta formuła jest spełniona. Dla powyższej formuły jednym z wartościowań, dla których jest ona spełniona, jest wartościowanie przypisujące zmiennym $x_1$, $x_2$, $x_3$, $x_4$ odpowiednio wartości 0, 1, 1, 0; w związku z tym powyższa formuła jest spełnialna.

Do dalszych rozważań ustalmy pewne kodowanie formuł logicznych do słów nad alfabetem $\{0,1\}$ - na przykład ustalmy, że najpierw zapisujemy liczbę klauzul, następnie dla każdej klauzuli liczbę literałów, a następnie dla każdego literału numer zmiennej oraz bit określający czy zmienna jest zaprzeczona.

Definicja

Niech $w\in \{0,1{\}}^{\star }$. Wtedy

 Parser nie mógł rozpoznać (nieznana funkcja „\iffw”): {\displaystyle w \in SAT \iffw}
 reprezentuje poprawnie zakodowaną formułę logiczną w koniunkcyjnej postaci normalnej i formuła ta jest spelnialna.

Ćwiczenie 8

Pokaż, że problem $SAT$ należy do klasy $NP$.

Wskazówka

Wykorzystaj definicję klasy $NP$ wykorzystującą świadka.

Rozwiązanie

Jak się okazuje problem $SAT$ jest problemem $NP$-zupełnym w sensie redukcji

logarytmicznej (a co za tym idzie również w sensie pozostałych dwóch znanych nam typów transformacji). Odpowiednie twierdzenie zostało udowodnione w roku 1971 niezależnie przez Stephena Cook'a i Leonida Lewina.