Złożoność obliczeniowa/Wykład 4: 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 1.1

Niech ${\mathcal {F}}$ będzie pewną rodziną funkcji o sygnaturze

$\{0,1\}^{\star }\rightarrow \{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 ${\mathcal {F}}$ i zapisujemy

$L_{1}\leq _{\mathcal {F}}L_{2}$.

wtedy i tylko wtedy, gdy

$\exists _{f\in {\mathcal {F}}}\forall _{w\in \{0,1\}^{\star }}w\in L_{1}\iff 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 $\leq _{\mathcal {F}}$ jest preporządkiem, to znaczy jest zwrotna (ze względu na obecność identyczności) i przechodnia (ze względu na domkniętość rodziny ${\mathcal {F}}$ na składanie).

Przedstawmy teraz najczęściej stosowane rodziny redukcji.

Redukcje wielomianowe

Przekształcenie grafu dwudzielnego w sieć przepływową.

Rodzina redukcji wielomianowych (Karpa) to rodzina funkcji $\{0,1\}^{\star }\rightarrow \{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 (animacja 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.2

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ć, dlaczego łą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 1.3

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 1.4

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 zapisać 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ąc 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 1.6

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 1.7

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 1.8

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ć $L_{1}$ 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 $\leq _{T}$.

Ćwiczenie 1.9

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

• $L_{1}\leq _{T}L_{2}\Rightarrow L_{1}\leq _{P}L_{2}$,

• $L_{1}\leq _{P}L_{2}\Rightarrow L_{1}\leq _{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 2.1

Niech ${\mathcal {C}}$ będzie pewną klasą złożoności, natomiast $\sqsubseteq$ 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 ${\mathcal {C}}$-zupełny w sensie preporządku $\sqsubseteq$ wtedy i tylko wtedy, gdy:

• $L\in {\mathcal {C}}$,

• $\forall _{L'\in {\mathcal {C}}}L'\sqsubseteq L$.

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

Ćwiczenie 2.2

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

Rozwiązanie

Problemami $P$-zupełnymi są wszystkie problemy reprezentowane przez nietrywialne języki (język jest nietrywialny, jeśli jest niepusty i różny od zbioru wszystkich słów nad danym alfabetem). 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 od tego, 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 zainteresowaniem 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 2.3

Przykłady problemów $P$-zupełnych można znaleźć w module 11.

Klasa NP i NP-zupełność

W ramach tego kursu naszym wielkim zainteresowaniem będzie się cieszyć klasa $NP$, a w szczególności problemy $NP$-zupeł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 3.1

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

$L\in NP\iff \exists _{p(x)-wielomian}\exists _{L'\in P}\forall _{n\in {\mathbb {N} }}\forall _{w\in \{0,1\}^{n}}[w\in L\iff$$(\exists _{v\in \{0,1\}^{p(n)}}\langle w,v\rangle \in L')]$.

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 3.2 [$NONPRIME$]

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

$w\in NONPRIME\iff$ 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'$ będzie miał wtedy następującą postać:

$L':=\{\langle w,v\rangle :(num(v)\neq num(w)\wedge num(v)\neq 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'$ 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$.

Przekształcanie rozgałęzienia stopnia k w k-1 rozgałęzień stopnia 2.

Dowód [Twierdzenia 3.1]

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

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:=\max _{(s,q)\in \Sigma \times Q}\#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'$ co najwyżej $k-1$-krotnie wolniejsza (a zatem nadal wielomianowa) o maksymalnym stopniu rozgałęzienia równym 2 - uzasadnienie przedstawione jest animacji Przekształcanie rozgałęzienia stopnia k w k-1 rozgałęzień stopnia 2.

Od tej pory będziemy się zajmować maszyną $M'$. 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'$ jest zatem zdefiniowana poprzez ciąg $W(n)$ bitów mówiących, która 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'$ - o ile taka istnieje.

Wystarczy w tym momencie wksazać deterministyczna maszynę Turinga $N$, rozpoznającą język $L'$ - czyli weryfikującą dla pary słów $\langle w,v\rangle$, 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'$; 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żyć, że $M'$ 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 alternatywną 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óćmy teraz do redukcji i problemów zupełnych. Oznaczmy jako $NPC$, $NPC_{L}$ i $NPC_{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 określić pewne relacje zawierania pomiędzy tymi klasami.

Ćwiczenie 3.3

Uszereguj klasy $NPC$, $NPC_{L}$ i $NPC_{T}$ od najwęższej do najszerszej i uzasadnij to uszeregowanie.

Rozwiązanie

Prawdziwe są następujące zawierania: $NPC_{L}\subseteq NPC\subseteq NPC_{T}$.

Weźmy dowolny problem z $NPC_{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 negację,

• 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 \neg x_{3})\wedge (x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \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 dalej dla każdego literału numer zmiennej oraz bit określający czy zmienna jest zanegowana.

Definicja 3.4

Niech $w\in \{0,1\}^{\star }$. Wtedy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle w \in SAT \iffw} reprezentuje poprawnie zakodowaną formułę logiczną w koniunkcyjnej postaci normalnej i formuła ta jest spelnialna.

Ćwiczenie 3.5

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

Wskazówka

Wykorzystaj definicję klasy $NP$ z użyciem ś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.

Twierdzenie 3.6 [(Cook'a-Lewina)]

Problem $SAT$ jest $NP$-zupełny w sensie redukcji logarytmicznej.

Dowód

Pierwszą część dowodu już mamy - wiemy, że $SAT\in NP$. Do pokazania pozostaje zatem fakt, że

$\forall _{L\in NP}L\leq _{L}SAT$.

Weźmy zatem dowolny język $L\in NP$. Korzystając z udowodnionego wcześniej twierdzenia wiemy, że istnieje $p(n)$ - wielomian określający długość świadka - oraz wielomianowy program dla deterministycznej maszyny Turinga, weryfikujący świadka - jego czas działania oznaczmy jako $Q(n)$. Załóżmy bez straty ogólności, że program ten kontynuuje działanie po dojściu do stanu akceptującego i pozostaje w tym stanie niezależnie od symbolu pod głowicą ("zapętla się" w tym stanie). Jako że wejściem programu weryfikującego jest konkatenacja słowa wejściowego i świadka, górnym ograniczeniem na czas jego działania w zależności od wielkości wejścia jest

$T(n):=Q(p(n)+n)$

(oczywiście ograniczenie to nadal jest wielomianowe).

Naszym zadaniem teraz będzie takie przekształcenie słowa wejściowego $w$ w formułę logiczną, aby formuła była spełnialna wtedy i tylko wtedy, gdy $w\in L$. Ustalmy zatem, jakich zmiennych będzie używać nasza formuła logiczna i jakie będziemy tym zmiennym przypisywać znaczenie.

Zmienna	Zakres parametrów	Znaczenie
$H_{t,p}$	$0\leq t\leq T(n)$, $-T(n)\leq p\leq T(n)$	Głowica w chwili $t$ znajduje się w miejscu $p$.
$Q_{t,q}$	$0\leq t\leq T(n)$, $0\leq q<|Q|$	Maszyna w chwili $t$ znajduje się w stanie $q$.
$S_{t,p,s}$	$0\leq t\leq T(n)$, $-T(n)\leq p\leq T(n)$, $0\leq s<|\Sigma |$	Na taśmie w chwili $t$ w miejscu $p$ znajduje się symbol $s$.

Oczywiście maszyna rozwiązująca problem SAT nie ma pojęcia o znaczeniu, jakie przypisujemy zmiennym; musimy to znaczenie wymusić podczas konstrukcji formuły logicznej.

Najpierw wymusimy, aby w każdej chwili symulowana głowica znajdowała się w dokładnie jednym miejscu. Dla chwili 0 będzie to wyglądało następująco:

$(H_{0,-T(n)}\vee H_{0,-T(n)+1}\vee \cdots \vee H_{0,0}\vee \cdots \vee H_{0,T(n)})\wedge$

$(\neg H_{0,-T(n)}\vee \neg H_{0,-T(n)+1})\wedge (\neg H_{0,-T(n)}\vee \neg H_{0,-T(n)+2})\wedge \cdots \wedge$$(\neg H_{0,-T(n)}\vee \neg H_{0,T(n)})\wedge$ $\cdots$ $(\neg H_{0,0}\vee \neg H_{0,1})\wedge \cdots \wedge (\neg H_{0,0}\vee \neg H_{0,T(n)})\wedge$ $\cdots$

$(\neg H_{0,T(n)-1}\vee \neg H_{0,T(n)})$.

Na tym etapie zapisaliśmy już $O(T(n)^{2})$ symboli, a zanosi się, że zapiszemy znacznie więcej. W związku z tym na potrzeby tego dowodu umówimy się, że powyższą formułę (i podobne, których będziemy potrzebować w przyszłości) będziemy skrótowo zapisywać w następujący sposób:

$\bigvee _{-T(n)\leq i\leq T(n)}H_{0,i}\wedge \bigwedge _{-T(n)\leq i<j\leq T(n)}(\neg H_{0,i}\vee \neg H_{0,j})$.

Oczywiście maszyna dokonująca redukcji będzie musiała się bardziej namęczyć i wypisać wszystkie klauzule; pocieszamy się jednak tym, że na pewno uda się jej to zrobić z użyciem logarytmicznej ilości pamięci.

Powyższa formuła gwarantowała, że w chwili 0 głowica będzie w dokładnie jednym miejscu. Aby zapewnić to dla każdego kroku działania maszyny, zapisujemy formułę:

$\bigwedge _{0\leq t\leq T(n)}[\bigvee _{-T(n)\leq i\leq T(n)}H_{t,i}\wedge \bigwedge _{-T(n)\leq i<j\leq T(n)}(\neg H_{t,i}\vee \neg H_{t,j})]$.

Analogiczne formuły musimy wypisać, aby zagwarantować, że:

• w każdej chwili maszyna znajduje się w dokładnie jednym stanie,

• w każdej chwili w każdej klatce taśmy znajduje się dokładnie jeden symbol.

Dla porządku odpowiednie formuły są podane poniżej:

$\bigwedge _{0\leq t\leq T(n)}[\bigvee _{0\leq i<|Q|}Q_{t,i}\wedge \bigwedge _{0\leq i<j<|Q|}(\neg Q_{t,i}\vee \neg Q_{t,j})]$, $\bigwedge _{0\leq t\leq T(n)}\bigwedge _{-T(n)\leq p\leq T(n)}[\bigvee _{0\leq i<|\Sigma |}S_{t,p,i}\wedge \bigwedge _{0\leq i<j<|\Sigma |}(\neg S_{t,p,i}\vee \neg S_{t,p,j})]$.

Następnie musimy zakodować w formule logicznej funkcję przejścia. Załóżmy, że dla pewnego stanu $q$ i symbolu $s$

$d(q,s)=(q',s',\leftarrow )$

Będziemy wtedy musieli zapisać następującą formułę:

$\bigwedge _{0\leq t<T(n)}\bigwedge _{-T(n)<p\leq T(n)}[(H_{t,p}\wedge Q_{t,q}\wedge S_{t,p,s})\Rightarrow (H_{t+1,p-1}\wedge Q_{t+1,q'}\wedge S_{t+1,p,s'})]$.

Niestety nie możemy wprost używać implikacji, a zatem musimy tę formułę trochę przekształcić:

$\bigwedge _{0\leq t<T(n)}\bigwedge _{-T(n)<p\leq T(n)}[(\neg H_{t,p}\vee \neg Q_{t,q}\vee \neg S_{t,p,s})\vee$$(H_{t+1,p-1}\wedge Q_{t+1,q'}\wedge S_{t+1,p,s'})]$

co z kolei możemy przekształcić do postaci ostatecznej:

$\bigwedge _{0\leq t<T(n)}\bigwedge _{-T(n)<p\leq T(n)}[(\neg H_{t,p}\vee \neg Q_{t,q}\vee \neg S_{t,p,s}\vee H_{t+1,p-1})\wedge (\neg H_{t,p}\vee \neg Q_{t,q}\vee \neg S_{t,p,s}\vee Q_{t+1,q'})\wedge (\neg H_{t,p}\vee \neg Q_{t,q}\vee \neg S_{t,p,s}\vee S_{t+1,p,s'})]$.

Formuły powyższego typu będziemy musieli wypisać dla każdej pary $(q,s)$ - będzie ich zatem $|Q|\cdot |\Sigma |$; liczba ta oczywiście nie jest zależna od $n$ (choć oczywiście długości formuł zależą kwadratowo od $T(n)$).

Musimy jeszcze zadbać o to, by komórki, w których nie ma głowicy, pozostawały bez zmian:

$\bigwedge _{0\leq t<T(n)}\bigwedge _{-T(n)\leq p\leq T(n)}\bigwedge _{0\leq s<|\Sigma |}[(\neg H_{t,p}\wedge S_{t,p,s})\Rightarrow S_{t+1,p,s}]$,

czyli

$\bigwedge _{0\leq t<T(n)}\bigwedge _{-T(n)\leq p\leq T(n)}\bigwedge _{0\leq s<|\Sigma |}[H_{t,p}\vee \neg S_{t,p,s}\vee S_{t+1,p,s}]$.

Musimy zadbać o to, by zmienne reprezentujące słowo wejściowe (czyli symbole taśmy w chwili 0) były takie jak należy:

$\bigwedge _{-T(n)\leq p<0}S_{0,p,\#}\wedge \bigwedge _{0\leq p<|w|}S_{0,p,w_{p}}\wedge S_{0,|w|,\#}\wedge \bigwedge _{|w|+1\leq p\leq |w|+p(n)}(S_{0,p,0}\vee S_{0,p,1})\wedge \bigwedge _{|w|+p(n)<p<=T(n)}S_{0,p,\#}$.

Żądamy, by w chwili początkowej na taśmie znalazło się słowo wejściowe oraz "kandydat na świadka". Na koniec żądamy, by po $T(n)$ krokach program znajdował się w stanie akceptującym (mógł się w nim znaleźć wcześniej, założyliśmy jednak, że maszyna w tym stanie się "zapętli", więc wystarczy, jeśli sprawdzimy w chwili $T(n)$)

$Q_{T(n),q_{acc}}$

Widzimy, że jeśli koniunkcja powyższych formuł jest spełnialna, to istnieje świadek dla słowa $w$ - będzie on określony przez wartościowanie zmiennych reprezentujących taśmę w chwili początkowej. Z drugiej strony widać, że istnienie świadka dla słowa $w$ implikuje wartościowanie zmiennych spełniające koniunkcję powyższych formuł logicznych. Pozostaje więc tylko uzasadnić to, że przekształcenie słowa $w$ w powyższą formułę odbywa się z użyciem logarytmicznej pamięci. Widać jednak, że postać każdej z tych częściowych formuł jest z góry określona i maszyna podczas dokonywania redukcji będzie jedynie potrzebowała przechowywać na taśmie określoną z góry liczbę iteratorów. Pokazaliśmy zatem, że $SAT$ jest problemem $NP$-zupełnym w sensie wszystkich trzech zdefiniowanych transformacji.

Charakteryzacja klasy NP w języku logiki

W ostatniej części tego modułu zaprezentujemy bardzo ciekawą charakteryzację klasy $NP$; jest ona zaskakująca choćby z tego powodu, że nie jest w niej w ogóle użyte pojęcie modelu obliczeń.

W następnych paragrafach będziemy stale korzystać z grafów. Umówmy się zatem, że od tej pory za reprezentację grafu o $n$ wierzchołkach uznajemy $n^{2}$ bitów, będących macierzą sąsiedztwa tego grafu, wypisaną wierszami.

Zdefiniujemy teraz kilka przydatnych pojęć z dziadziny logiki.

Termem nazywamy:

• zmienną,

• wyrażenie $f(t_{1},t_{2},\cdots ,t_{k})$, gdzie $f$ to $k$-argumentowy symbol funkcyjny, a $t_{1},t_{2},\cdots ,t_{k}$ to termy.

Formułą pierwszego rzędunazywamy:

• wyrażenie $t_{1}=t_{2}$, gdzie $t_{1}$ i $t_{2}$ są termami,

• wyrażenie $R(t_{1},t_{2},\cdots ,t_{k})$, gdzie $R$ to $k$-arny symbol relacyjny,

• wyrażenia $(\neg \phi )$, $(\phi \vee \psi )$, $(\phi \wedge \psi )$, $(\phi \Rightarrow \psi )$, gdzie $\phi$ i $\psi$ to formuły,

• wyrażenia $\forall _{x}(\phi )$ i $\exists _{x}(\phi )$, gdzie $x$ jest zmienną a $\phi$ jest formułą.

(oczywiście możemy pomijać nawiasy, jeśli nie są one konieczne).

Formułą może być dla przykładu następujące wyrażenie:

$(E(x,y)\wedge E(x,z))\Rightarrow \neg E(y,z)$.

Takiej formule ciężko jednak przypisać jakieś znaczenie, dopóki $x$, $y$ i $z$ są zmiennymi niezwiązanymi i dopóki nie wiemy, czym jest $E$. Umówmy się zatem, że zdaniem pierwszego rzędu dla grafów jest formuła logiczna, która:

• nie posiada zmiennych niezwiązanych,

• nie używa symboli funkcyjnych,

• jedynym symbolem relacyjnym, którego używa, jest binarna relacja $E$, reprezentująca relację sąsiedztwa w grafie.

Zdaniem pierwszego rzędu dla grafów jest na przykład:

$\forall _{x}\forall _{y}\forall _{z}[(E(x,y)\wedge E(x,z))\Rightarrow \neg E(y,z)]$.

Ustalmy teraz pewien graf o zbiorze wierzchołków $V$ i relacji sąsiedztwa $E\subseteq V^{2}$. Zinterpretujmy wyrażenia $\forall _{x}\cdots$ jako $\forall _{x\in V}\cdots$. W tym momencie możemy już rozpatrywać prawdziwość powyższego zdania dla poszczególnych grafów: zdanie to będzie prawdziwe dla grafów nie posiadających trójkątów i fałszywe dla pozostałych grafów. Widzimy zatem, że zdania pierwszego rzędu mogą wyrażać pewne własności grafów - czyli spośród wszystkich grafów wyłaniać pewne ich podzbiory. Okazuje się jednak, że siła ekspresji zdań pierwszego rzędu nie jest zbyt duża - na przykład nie da się skonstruować zdania, odróżniającego grafy spójne od niespójnych. Zdefiniujmy zatem silniejszą klasę zdań.

Zdaniem egzystencjalnym drugiego rzędu dla grafów jest zdanie następującej postaci:

$\exists _{R_{1}}\exists _{R_{2}}\cdots \exists _{R_{k}}\phi$,

gdzie $R_{1},\cdots ,R_{k}$ to symbole relacyjne o ustalonej arności, natomiast $\phi$ to formuła zdaniowa pierwszego rzędu bez zmiennych niezwiązanych, symboli funkcyjnych i używająca tylko symboli relacyjnych $R_{1},\cdots ,R_{k}$ i $E$. Klasę egzystencjalnych zdań drugiego rzędu będziemy oznaczać jako $ESO$. Przykładem takiego zdania jest:

$\exists _{U-unarna}[\forall _{x}\forall _{y}(E(x,y)\wedge U(x))\Rightarrow U(y)]\wedge [\exists _{x}\exists _{y}(U(x)\wedge \neg U(y))]$

Powyższa formuła jest spełniona wtedy i tylko wtedy, gdy rozpatrywany graf jest niespójny; relację unarną można rozumieć jako wybór pewnych wierzchołków, przy czym pierwsza część formuły zapewnia, że jeżeli zostanie wybrany jakiś wierzchołek, to zostanie również wybrana cała jego spójna składowa. Druga część formuły żąda istnienia dwóch wierzchołków, z których jeden jest wybrany a drugi nie - a co za tym idzie, leżących w różnych spójnych składowych.

Zastanówmy się teraz, czy jesteśmy w stanie napisać egzystencjalne zdanie drugiego rzędu, które jest prawdziwe wtedy i tylko wtedy, gdy rozpatrywany graf jest spójny. Widać, że problem polega na tym, iż nie wolno nam zapisać wyrażenia $\forall _{U}\cdots$. W ogólności nie wiadomo, czy dopełnienie klasy grafów charakteryzowanej przez jakieś zdanie z $ESO$ jest charakteryzowalne przez zdanie z $ESO$. W tym przypadku jednak mamy szczęście - poniższe zdanie charakteryzuje grafy spójne:

$\exists _{P-binarna}[\forall _{x}P(x,x)]\wedge [\forall _{x}\forall _{y}P(x,y)\vee P(y,x)]\wedge [\forall _{x}\forall _{y}\forall _{z}(P(x,y)\wedge P(y,z))\Rightarrow P(x,z)]\wedge \exists _{m}[\forall _{n}(P(n,m)\Rightarrow (n=m))\wedge \forall _{n}(\neg P(n,m)\Rightarrow \exists _{k}(P(k,n)\wedge E(k,n)))]$.

Nie podamy tutaj szczegółowego wyjaśnienia powyższego zdania; warto jednak wspomnieć, że od $P$ oczekujemy, by była to relacja liniowego porządku na wierzchołkach, z elementem najmniejszym $m$.

Egzystencjalne zdania drugiego rzędu a złożoność

Wybierzmy jakieś zdanie z $ESO$. Będziemy chcieli skonstruować niedeterministyczną maszynę Turinga, która będzie oczekiwała na wejściu opisów grafów i będzie akceptowała te grafy, dla których wybrana formuła jest spełniona. Okazuje się, że nasza (niedeterministyczna) maszyna może to zrobić w czasie wielomianowym. Niech $s_{1},s_{2},\cdots ,s_{k}$ będą arnościami kolejnych relacji w zdaniu. Aby zdefiniować te relacje, potrzeba odpowiednio $n^{s_{1}},n^{s_{2}},\cdots ,n^{s_{k}}$ bitów. Maszyna zatem najpierw wygeneruje "kandydatów na świadków" o długości $n^{s_{1}}+n^{s_{2}}+\cdots +n^{s_{k}}$ bitów (definiując tym samym wszystkie relacje), po czym zweryfikuje prawdziwość formuły pierwszego rzędu. W formule pierwszego rzędu kwantyfikatory odpowiadają pętlom od 1 do $n$ - zatem czas weryfikacji całej formuły wynosi $O(n^{d})$, gdzie $d$ to maksymalne "zagłębienie kwantyfikatorów" w tej formule. Jest zatem jasne, że dla każdej formuły z $ESO$ rozpoznawanie spełniających ją grafów jest zadaniem z klasy $NP$.

Twierdzenie Fagina

Przejdźmy teraz do dużo ciekawszego spostrzeżenia. Stwierdzimy bowiem, że każdemu problemowi z klasy $NP$ możemy przypisać charakteryzującą go formułę typu $ESO$.

Najpierw jednak trzeba się zastanowić, w jaki sposób powiązać ze sobą języki oraz zbiory grafów. Chcielibyśmy zdefiniować konwersję $n$-bitowego słowa w graf taką, że:

• wynikowy graf ma $O(n)$ wierzchołków,

• konwersja w obie strony wykonywana jest na deterministycznej maszynie Turinga w czasie wielomianowym,

• grafy przypisane dwóm różnym słowom nie są izomorficzne.

Ostatnie założenie wynika z prostej obserwacji: zdanie z $ESO$ nie jest w stanie rozróżnić grafów, które są izomorficzne. Skonstruowanie powyższej konwersji pozostawione jest Czytelnikowi.

Wybierzmy teraz dowolny problem decyzyjny $L$ z klasy $NP$. Jest jasne, że odpowiadający mu problem $L'$, oczekujący wejścia w postaci grafów, również należy do $NP$ - można go rozwiązać poprzez zdekodowanie grafu do słowa binarnego i uruchomienie maszyny dla oryginalnego problemu. Weźmy zatem maszynę zachowującą się w ten sposób i oznaczmy ją jako $M$. Załóżmy bez straty ogólności, że maszyna ta jest jednostronnie ograniczona oraz że jej maksymalny stopień rozgałęzienia wynosi 2. Będziemy teraz - podobnie jak wcześniej przy twierdzeniu Cook'a-Lewina - starali się skonstruować formułę logiczną symulującą działanie $M$. W tym przypadku jednak formuła nie może być generowana na bieżąco po wczytaniu wejścia; tutaj skonstruujemy jedną formułę, która będzie działać dla każdego wejścia.

Przejdźmy zatem do konstrukcji. Załóżmy, że maszyna $M$ działa pesymistycznie w czasie $n^{k}$, gdzie $n$ to liczba wierzchołków w grafie wejściowym. W naszej formule będziemy używać liniowego porządku, podobnego do zdefiniowanego w formule charakteryzującej spójność. Użyjemy go jednak głównie po to, by zdefiniować liniowy porządek leksykograficzny na $k$-elementowych ciągach wierzchołków. Załóżmy zatem, że mamy porządek:

$v_{1},v_{2},\cdots ,v_{n}$.

Chcemy na jego podstawie stworzyć porządek leksykograficzny dla $k$-elementowych ciągów:

$(v_{1},v_{1},\cdots ,v_{1}),(v_{1},v_{1},\cdots ,v_{1},v_{2}),\cdots ,(v_{n},v_{n},\cdots ,v_{n})$.

Tworzenie takiego porządku jest mało ciekawe - dlatego założymy po prostu, że mamy $2k$-arną relację ${\bar {P}}({\bar {x}},{\bar {y}})$, wyznaczającą powyższy porządek. Z tej relacji również łatwo możemy wywieść relację następnika; ${\bar {x}}$ będzie w relacji z ${\bar {y}}$ wtedy i tylko wtedy, gdy ${\bar {y}}$ będzie najmniejszym leksykograficznie ciągiem większym od ${\bar {x}}$. Relację następnika oznaczamy jako $Succ$.

Możemy zatem patrzeć na $k$-elementowe ciągi wierzchołków jako na sekwencję obiektów. Jest ich $n^{k}$ - a zatem tyle, ile maksymalnie możemy potrzebować czasu i klatek pamięci podczas działania maszyny $M$. Od tej pory ciągi $k$ wierzchołków będziemy traktować po prostu jako liczniki wskazujące na pewien krok postępowania maszyny lub na pewną komórkę taśmy; zapomnimy przy tym zupełnie o pierwotnym znaczeniu tych obiektów.

W tym momencie jesteśmy gotowi do zdefiniowania relacji oraz znaczenia, które im będziemy przypisywali. Będą one beardzo podobne do zmiennych, używanych w dowodzie twierdzenia Cook'a-Lewina.

• $H({\bar {x}},{\bar {y}})$ -- ${\bar {x}}$ jest w relacji z ${\bar {y}}$ wtedy i tylko wtedy, gdy w chwili ${\bar {y}}$ głowica jest w miejscu ${\bar {x}}$,

• $S_{\sigma }({\bar {x}},{\bar {y}})$ -- ${\bar {x}}$ jest w relacji z ${\bar {y}}$ wtedy i tylko wtedy, gdy w chwili ${\bar {y}}$ na taśmie w miejscu ${\bar {x}}$ jest symbol $\sigma$ (relacji tego typu jest tyle, ile symboli taśmowych),

• $Q_{q}({\bar {y}})$ - ${\bar {y}}$ należy do relacji wtedy i tylko wtedy, gdy w chwili ${\bar {y}}$ maszyna jest w stanie $q$ (relacji tego typu jest tyle, ile stanów).

Musimy teraz wymusić odpowiednią postać tych relacji - taką, aby reprezentowały one obliczenia maszyny Turinga. A zatem - żądamy, by głowica w każdej chwili znajdowała się w dokładnie jednym miejscu:

$\forall _{\bar {x}}\forall _{{\bar {x}}'}\forall _{\bar {y}}[{\bar {x}}={\bar {x}}'\vee \neg H({\bar {x}},{\bar {y}})\vee \neg H({\bar {x}}',{\bar {y}})]$.

Stosujemy tutaj pewne skróty myślowe (w końcu ${\bar {x}}$, ${\bar {x}}'$ i ${\bar {y}}$ reprezentują $k$-elementowe ciągi). $\forall _{\bar {x}}$ jest zatem tak naprawdę sekwencją $k$ kwantyfikatorów: $\forall _{x_{0}}\forall _{x_{1}}\cdots \forall _{x_{k-1}}$. Natomiast wyrażenie ${\bar {x}}={\bar {x}}'$ jest koniunkcją $k$ równości. Podobne formuły należy wypisać, aby zagwarantować obecność dokładnie jednego symbolu w klatce i to, że w każdym kroku maszyna jest w dokładnie jednym stanie:

$\forall _{\bar {x}}\forall _{\bar {y}}(\neg S_{\sigma _{0}}\vee \neg S_{\sigma _{1}})\wedge (\neg S_{\sigma _{0}}\vee \neg S_{\sigma _{2}})\wedge \cdots$ $\forall _{\bar {y}}(\neg Q_{q_{0}}\vee \neg Q_{q_{1}})\wedge (\neg Q_{q_{0}}\vee \neg Q_{q_{2}})\wedge \cdots$

Musimy określić początkową zawartość taśmy:

$\forall _{x_{k-2}}\forall _{x_{k-1}}S_{1}((0,\cdots ,0,x_{k-2},x_{k-1}),(0,\cdots ,0))\iff E(x_{k-2},x_{k-1})$,

$\forall _{x_{k-2}}\forall _{x_{k-1}}S_{0}((0,\cdots ,0,x_{k-2},x_{k-1}),(0,\cdots ,0))\iff \neg E(x_{k-2},x_{k-1})$,

$\forall _{\bar {x}}(x_{0}\neq 0\vee x_{1}\neq 0\vee \cdots \vee x_{k-3}\neq 0)\Rightarrow T_{\#}({\bar {x}},(0,\cdots ,0))$.

Skorzystaliśmy tutaj z symbolu $0$; reprezentuje on najmniejszy wierzchołek w sensie porządku $P$ i jest zdefiniowany następująco:

$\exists _{0}\forall _{x}P(0,x)$.

Stan początkowy i początkowe położenie głowicy definiowane są następującą formułą:

$H((0,\cdots ,0),(0,\cdots ,0))\wedge Q_{q_{0}}((0,\cdots ,0))$,

natomiast oczekiwany stan końcowy to:

$Q_{q_{acc}}((\tau ,\cdots ,\tau ))$,

gdzie $\tau$ to wierzchołek maksymalny w sensie porządku $P$, zdefiniowany analogicznie jak $0$. Do zdefiniowania pozostało nam jeszcze tylko dynamiczne zachowanie maszyny. Zdefiniujmy zatem funkcję przejścia; niech dla przykładu:

$d((q,\sigma ))=\{(q',\sigma ',\leftarrow ),(q'',\sigma '',\rightarrow )\}$.

Zapisujemy wtedy formułę:

$\forall _{\bar {x}}\forall _{{\bar {x}}'}\forall _{{\bar {x}}''}\forall _{\bar {y}}\forall _{{\bar {y}}'}[Succ({\bar {x}}',{\bar {x}})\wedge Succ({\bar {x}},{\bar {x}}'')\wedge Succ({\bar {y}}',{\bar {y}})\wedge Q_{q}({\bar {y}})\wedge S_{\sigma }({\bar {x}},{\bar {y}})\wedge H({\bar {x}},{\bar {y}})\Rightarrow (Q_{q'}({\bar {y}}')\wedge S_{\sigma '}({\bar {x}},{\bar {y}}')\wedge H({\bar {x}}'',{\bar {y}}'))\vee (Q_{q''}({\bar {y}}')\wedge S_{\sigma ''}({\bar {x}},{\bar {y}}')\wedge H({\bar {x}}',{\bar {y}}'))]$.

Ostatnia formuła gwarantuje zachowanie tego samego symbolu na taśmie, gdy w danej komórce nie ma głowicy:

$\forall _{\bar {x}}\forall _{\bar {y}}\forall _{{\bar {y}}'}[Succ({\bar {y}}',{\bar {y}})\wedge S_{\sigma }({\bar {x}},{\bar {y}})\wedge \neg H({\bar {x}},{\bar {y}})\Rightarrow S_{\sigma }({\bar {x}},{\bar {y}}')]$.

Uwaga 3.7

Powyższe formuły bardzo przypominają te, które zostały zdefiniowane przy twierdzeniu Cook'a-Lewina. Jedyna znacząca różnica jest w funkcji przejścia:

tym dowodzie symulujemy maszynę niedeterministyczną, podczas gdy w poprzednim generowaliśmy świadka i postępowaliśmy deterministycznie. Do tej różnicy nie należy jednak przywiązywać wagi - moglibyśmy również tutaj stosować definicję ze świadkiem. Nie czynimy tego tylko dlatego, że utrudniłoby nam to wypisanie formuły definiującej początkowy stan taśmy.  

Jeżeli teraz poskładamy powyższe formuły w jedną całość i dopiszemy kwantyfikatory:

$\exists _{P}\exists _{\bar {P}}\exists _{Succ}\exists _{S_{\sigma _{0}}}\cdots \exists _{S_{\sigma _{|\Sigma |-1}}}\exists _{Q_{q_{0}}}\cdots \exists _{Q_{q_{|Q|-1}}}\exists _{H}\cdots$

to otrzymamy formułę z rodziny $ESO$, charakteryzującą grafy z $L'$.

Udowodniliśmy zatem fakt znany jako twierdzenie Fagina.

Twierdzenie 3.8 [Fagina]

Klasę $NP$ stanowią dokładnie te problemy, które sa charakteryzowalne przez egzystencjalne zdania drugiego rzędu.