Złożoność obliczeniowa/Wykład 4: Redukcje i zupełność

From Studia Informatyczne

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.

Spis treści

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:

Szablon: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.

image:End_of_proof.gif

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

image:End_of_proof.gif
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.

Testy końcowe