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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 będzie pewną rodziną funkcji o sygnaturze

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

.

wtedy i tylko wtedy, gdy

Intuicyjnie problem jest w pewnym sensie co najwyżej tak trudny, jak problem - jeżeli znamy rozwiązanie problemu oraz odpowiednią funkcję (zwaną redukcją lub transformacją), to znamy również rozwiązanie problemu . Warto zauważyć, że relacja 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

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

Rodzina redukcji wielomianowych (Karpa) to rodzina funkcji 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 jest redukowalny wielomianowo do problemu oraz należy do klasy , to również należy do klasy . Aby uzasadnić tę własność, wystarczy skonstruować maszynę, która najpierw przekształci instancję problemu do instancji problemu (uczyni to w czasie wielomianowym, bo jest wielomianowo redukowalne do ), po czym w czasie wielomianowym da odpowiedź dla instancji problemu .

Ćwiczenie 1.2

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

Rozwiązanie

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
Rozwiązanie

Ćwiczenie 1.4

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

Wskazówka
Rozwiązanie

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 oraz . Problem przy "składaniu" dwóch maszyn - transformacji oraz maszyny rozwiązującej - 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 ; za każdym razem, gdy maszyna ta będzie chciała odwołać się do któregoś - dla ustalenia uwagi -tego - bitu wejścia, na osobnej taśmie uruchomimy maszynę implementującą redukcję z do . 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 -ta operacja wyjścia, maszyna powróci do wykonywania programu rozwiązującego problem , 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 , 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ą jest wielotaśmową maszyną Turinga, z jedną wyróżnioną taśmą i trzema wyróżnionymi stanami . Zachowanie maszyny różni się od zachowania zwykłej maszyny Turinga w następujący sposób: przejście maszyny do stanu jest traktowane jako odwołanie do wyroczni . Jeżeli słowo aktualnie zapisane na wyróżnionej taśmie należy do języka , to maszyna przechodzi do stanu ; w przeciwnym razie przechodzi do stanu . 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 .

Definicja 1.7

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

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

Ćwiczenie 1.8

Niech i będą językami nad alfabetem oraz niech transformuje się do w sensie transformacji wielomianowej Turinga. Które z poniższych zdań jest prawdziwe:

  • ,
  • ?
Rozwiązanie

Łatwo zauważyć, że transformacja wielomianowa w sensie Turinga wyznacza preporządek na językach zawartych w . Oznaczamy ją symbolem .

Ćwiczenie 1.9

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

  • ,
  • ?
Rozwiązanie

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 będzie pewną klasą złożoności, natomiast preporządkiem określonym na językach zawartych w (w domyśle jedną ze zdefiniowanych wcześniej rodzin transformacji). Mówimy, że problem decyzyjny jest -zupełny w sensie preporządku wtedy i tylko wtedy, gdy:

  • ,
  • .

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 2.2

Scharakteryzuj problemy -zupełne w sensie transformacji wielomianowej.

Rozwiązanie

Jak zauważyliśmy rozpatrywana powyżej klasa jest mało interesująca. Jeszcze mniej interesująca jest oczywiście klasa problemów -zupełnych w sensie transformacji wielomianowej Turinga. Dla odróżnienia - klasa problemów -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 -zupełnych.

Uwaga 2.3

Przykłady problemów -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 , a w szczególności problemy -zupełne w sensie trzech poznanych wcześniej rodzin transformacji. Zanim jednak przejdziemy do problemów -zupełnych, poznamy pewną alternatywną definicję klasy złożoności .

Twierdzenie 3.1

Niech . Wtedy:

.

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 zwykle nazywane jest świadkiem (ang. witness) słowa . Żądamy, żeby każde słowo należące do języka miało świadka o długości wielomianowej, natomiast żadne słowo spoza takiego świadka nie miało. Co więcej - żądamy, aby sprawdzanie, czy jest świadkiem słowa było wykonywane w czasie wielomianowym na maszynie deterministycznej, dlatego klasę czasem nazywamy klasą problemów weryfikowalnych w czasie wielomianowym.

Przykład 3.2 []

Rozważmy problem . Niech będzie reprezentacją liczby naturalnej w systemie binarnym.

liczba reprezentowana przez 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 będzie miał wtedy następującą postać:

,

gdzie oznacza liczbę reprezentowaną przez słowo . Łatwo zauważyć, że jest implementowalna w czasie wielomianowym na deterministycznej maszynie - wystarczy pisemnie podzielić przez , 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 .

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

Dowód [Twierdzenia 3.1]

W stronę dowód jest prosty - skonstruujemy niedeterministyczną maszynę Turinga, rozwiązującą problem . Maszyna ta najpierw przesunie głowicę za słowo wejściowe, przez następne 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 w czasie wielomianowym.

Jeżeli dla słowa wejściowego 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ą .

Udowodnijmy teraz przejście w drugą stronę (). Skoro , to istnieje niedeterministyczna maszyna Turinga rozstrzygająca problem . Niech oznacza maksymalny stopień rozgałęzienia maszyny , tj.

,

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 co najwyżej -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ą . Oznaczmy jej czas działania jako ; w związku z tym maszyna dla słowa wielkości wykona co najwyżej rozgałęzień. Każda ścieżka postępowania maszyny jest zatem zdefiniowana poprzez ciąg 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 , świadkiem natomiast niech będzie ciąg reprezentujący akceptującą ścieżkę postępowania maszyny - o ile taka istnieje.

Wystarczy w tym momencie wksazać deterministyczna maszynę Turinga , rozpoznającą język - czyli weryfikującą dla pary słów , czy jest świadkiem dla . Maszyna taka jest prosta do skonstruowania w następujący sposób:

  • najpierw przepisuje na tasmę pomocniczą, po czym wraca na głównej taśmie do początku słowa ,
  • zachowuje się podobnie jak maszyna ; w przypadku, gdy maszyna ma do wyboru dwie opcje, sięga po kolejny dostępny bit taśmy pomocniczej i na jego podstawie wybiera ścieżkę postępowania.

Łatwo zauważyć, że akceptuje słowo wtedy i tylko wtedy, gdy istnieje świadek, który spowoduje, że maszyna dojdzie do stanu akceptującego.

End of proof.gif

Poznaliśmy zatem alternatywną definicję klasy . Potocznie często mówi się, że maszyna rozwiązująca problem z klasy 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 , i klasy problemów -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 , i od najwęższej do najszerszej i uzasadnij to uszeregowanie.

Rozwiązanie

Problem SAT

Zdefiniowanie problemu 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:
.

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

Pokaż, że problem należy do klasy .

Wskazówka
Rozwiązanie

Twierdzenie 3.6 [(Cook'a-Lewina)]

Problem jest -zupełny w sensie redukcji logarytmicznej.

Dowód

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

.

Weźmy zatem dowolny język . Korzystając z udowodnionego wcześniej twierdzenia wiemy, że istnieje - wielomian określający długość świadka - oraz wielomianowy program dla deterministycznej maszyny Turinga, weryfikujący świadka - jego czas działania oznaczmy jako . 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

(oczywiście ograniczenie to nadal jest wielomianowe).

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

End of proof.gif
Zmienna Zakres parametrów Znaczenie
, Głowica w chwili znajduje się w miejscu .
, Maszyna w chwili znajduje się w stanie .
, , Na taśmie w chwili w miejscu znajduje się symbol .

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:

.

Na tym etapie zapisaliśmy już 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:

.

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łę:

.

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:

, .

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

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

.

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

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

.

Formuły powyższego typu będziemy musieli wypisać dla każdej pary - będzie ich zatem ; liczba ta oczywiście nie jest zależna od (choć oczywiście długości formuł zależą kwadratowo od ).

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

,

czyli

.

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:

.

Żą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 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 )

Widzimy, że jeśli koniunkcja powyższych formuł jest spełnialna, to istnieje świadek dla słowa - 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 implikuje wartościowanie zmiennych spełniające koniunkcję powyższych formuł logicznych. Pozostaje więc tylko uzasadnić to, że przekształcenie słowa 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 jest problemem -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 ; 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 wierzchołkach uznajemy 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 , gdzie to -argumentowy symbol funkcyjny, a to termy.

Formułą pierwszego rzędunazywamy:

  • wyrażenie , gdzie i są termami,
  • wyrażenie , gdzie to -arny symbol relacyjny,
  • wyrażenia , , , , gdzie i to formuły,
  • wyrażenia i , gdzie jest zmienną a 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:

.

Takiej formule ciężko jednak przypisać jakieś znaczenie, dopóki , i są zmiennymi niezwiązanymi i dopóki nie wiemy, czym jest . 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 , reprezentująca relację sąsiedztwa w grafie.

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

.

Ustalmy teraz pewien graf o zbiorze wierzchołków i relacji sąsiedztwa . Zinterpretujmy wyrażenia jako . 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:

,

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

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 . W ogólności nie wiadomo, czy dopełnienie klasy grafów charakteryzowanej przez jakieś zdanie z jest charakteryzowalne przez zdanie z . W tym przypadku jednak mamy szczęście - poniższe zdanie charakteryzuje grafy spójne:

.

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

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

Wybierzmy jakieś zdanie z . 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 będą arnościami kolejnych relacji w zdaniu. Aby zdefiniować te relacje, potrzeba odpowiednio bitów. Maszyna zatem najpierw wygeneruje "kandydatów na świadków" o długości 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 - zatem czas weryfikacji całej formuły wynosi , gdzie to maksymalne "zagłębienie kwantyfikatorów" w tej formule. Jest zatem jasne, że dla każdej formuły z rozpoznawanie spełniających ją grafów jest zadaniem z klasy .

Twierdzenie Fagina

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

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

  • wynikowy graf ma 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 nie jest w stanie rozróżnić grafów, które są izomorficzne. Skonstruowanie powyższej konwersji pozostawione jest Czytelnikowi.

Wybierzmy teraz dowolny problem decyzyjny z klasy . Jest jasne, że odpowiadający mu problem , oczekujący wejścia w postaci grafów, również należy do - 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 . 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 . 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 działa pesymistycznie w czasie , gdzie 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 -elementowych ciągach wierzchołków. Załóżmy zatem, że mamy porządek:

.

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

.

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

Możemy zatem patrzeć na -elementowe ciągi wierzchołków jako na sekwencję obiektów. Jest ich - a zatem tyle, ile maksymalnie możemy potrzebować czasu i klatek pamięci podczas działania maszyny . Od tej pory ciągi 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.

  • -- jest w relacji z wtedy i tylko wtedy, gdy w chwili głowica jest w miejscu ,
  • -- jest w relacji z wtedy i tylko wtedy, gdy w chwili na taśmie w miejscu jest symbol (relacji tego typu jest tyle, ile symboli taśmowych),
  • - należy do relacji wtedy i tylko wtedy, gdy w chwili maszyna jest w stanie (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:

.

Stosujemy tutaj pewne skróty myślowe (w końcu , i reprezentują -elementowe ciągi). jest zatem tak naprawdę sekwencją kwantyfikatorów: . Natomiast wyrażenie jest koniunkcją 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:

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

,

,

.

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

.

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

,

natomiast oczekiwany stan końcowy to:

,

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

.

Zapisujemy wtedy formułę:

.

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

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

to otrzymamy formułę z rodziny , charakteryzującą grafy z .

Udowodniliśmy zatem fakt znany jako twierdzenie Fagina.

Twierdzenie 3.8 [Fagina]

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

Testy końcowe