Złożoność obliczeniowa/Wykład 13: Pamięć logarytmiczna i hierarchia wielomianowa

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Klasy L, NL i coNL

W tym rozdziale zajmiemy się klasami złożoności, w których dajemy bardzo restrykcyjne wymagania odnośnie zużywanej pamięci, a mianowicie ograniczamy jej ilość przez funkcję logarytmiczną. Przypomnijmy:

  • Klasa (log), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,
  • Klasa (log), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
  • Klasa (log), to dopełnienie klasy tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,

Na podstawie następnego rozdziału i twierdzenia Immermana-Szelepcsényi'ego dowiemy się, że . Natomiast pytanie czy pozostaje wciąż problemem otwartym.

Przyjrzymy się teraz problemom zupełnym w klasie . Zupełność definiujemy przy pomocy redukcji w pamięci logarytmicznej, gdyż jak wiemy, wszystkie z powyższych klas są zawarte w klasie (chociaż nie wiemy, czy ściśle). Dopuszczenie redukcji wielomianowej zniwelowałoby jakiekolwiek różnice pomiędzy językami, gdyż sama redukcja miałaby moc obliczeniową pozwalającą rozwiązać wszystkie problemy z tych klas. Poniższy problem okazuje się być -zupełny:

Definicja 1.1 [Problem REACHABILITY:]

Wejście: Graf skierowany oraz wierzchołki i .
Wyjście: Czy istnieje ścieżka od do w ?

Ćwiczenie 1.2

Pokaż, że problem REACHABILITY jest -zupełny.

Wskazówka
Rozwiązanie

Bardzo ciekawy rezultat, który zbliżył nas do odpowiedzi na pytanie czy , uzyskał w 2004 Reingold. Pokazał on, że problem UNDIRECTED REACHABILITY, czyli osiągalność w grafie nieskierowanym należy do klasy .

Twierdzenie Immermana-Szelepcsényi'ego

Ten rozdział poświęcony jest bardzo ciekawemu i całkiem młodemu wynikowi udowodnionemu niezależnie przez Neila Immermana i Róberta Szelepcsényi'ego w roku 1987, za który otrzymali nagrodę Goedl'a w 1995

Twierdzenie mówi o tym, że klasy niedeterministyczne złożoności pamięciowej są zamknięte na dopełnienie:

Twierdzenie 2.1 [twierdzenie Immermana-Szelepcsényi'ego]

Jeśli jest konstruowalna pamięciowo, to .

Dowód

To co zostało pokazane przez autorów, to maszyna niedeterministyczna, która mając dany graf skierowany i wierzchołek potrafi obliczyć liczbę wierzchołków osiąganych z w grafie przy użyciu pamięci log . Zrobimy z niej użytek w ostatniej części głównego dowodu, gdy będziemy uruchamiać ją na grafie konfiguracji.

Maszyna jest dosyć trikowa i pokazuje jak wiele daje nam niedeterminizm. Wielokrotnie będziemy wykorzystywać fakt, że wystarczy nam, aby maszyna niedeterministyczna na dowolnej ścieżce dokonała poprawnego obliczenia. Na wszystkich pozostałych ścieżkach będziemy "wykrywać", że coś jest nie tak i kończyć działanie w stanie odrzucającym ("poddawać się").

Oznaczmy, przez zbiór tych wierzchołków grafu , które są osiągane z ścieżką o długości co najwyżej . Natomiast przez oznaczymy liczność tego zbioru. Naszym obiektem zainteresowania jest zatem obliczenie wartości , czyli liczba wszystkich wierzchołków osiągalnych, gdyż - rozmiar grafu - ogranicza długość ścieżki.

Pamiętamy jednak, że mamy do dyspozycji tylko logarytmiczną ilość pamięci, więc o zapamiętaniu zbioru (i obliczaniu na jego podstawie co byłoby banalne) nie możemy marzyć - ma on wielkość liniową względem rozmiaru . To brzmi niesamowicie, ale będziemy obliczać na podstawie ! Czyli wystarczy nam liczba stosownych wierzchołków, która to do zapisu potrzebuje pamięci logarytmicznej. Główna pętla algorytmu przedstawia się następująco:

 
 for
  to  do
   Wyznacz  na podstawie 
 end for

Teraz procedura obliczająca . Jest ona całkiem prosta, jeśli zastosujemy w niej pewien skrót notacyjny:

 
 for all  do
   if  then
     s(i)++
   end if
 end for

Lecz zbioru nie byliśmy w stanie zapamiętać. Zapowiedzielśmy już, że będziemy sprawdzać, czy wierzchołek do niego należy, na podstawie . To najbardziej skomplikowana część algorytmu, gdzie wykorzystujemy niedeterminizm.

Przeglądniemy teraz wszystkie wierzchołki grafu i sprawdzimy, czy któryś z nich należy do w sposób niedeterministyczny. Przypomnijmy, że taka procedura, gdy mówi "TAK", to wierzchołek na pewno należy do , natomiast gdy mówi "NIE" to mogliśmy trafić na nieodpowiednią ścieżkę obliczeń. Będziemy jednak zliczać ile wierzchołków zgadliśmy na TAK i sprawdzimy, czy wyjdzie nam . Jeśli tak się stanie, to będziemy mieć gwarancję, że o każdym wierzchołku zgadliśmy dobrze. Jeśli wyszło nam mniej, to odrzucamy, wiedząc, że na innej ścieżce obliczeń musi nam się udać. Następnie sprawdzamy, czy z można dojść do przy pomocy jednej krawędzi w ten sposób obliczymy czy :

 , 
   for all  do
   if  then
     licznik ++
     if  lub  then
       
     end if
   end if
 end for
 if  then
   return NIE 
 else
   return wynik 
 end if

Teraz przejdźmy do konstrukcji maszyny obliczającej, czy w sposób niedeterministyczny. Algorytm jest całkiem prosty i podobny do tego, w którym pokazywaliśmy, że REACHABILITY jest w . Zgadujemy sekwencję wierzchołków. Rozpoczynamy od . Sprawdzamy, czy każdy kolejny wierzchołek jest sąsiadem poprzedniego (lub równy poprzedniemu) oraz czy w końcu dochodzimy do . W ten sposób sprawdzimy (niedeterministycznie) wszystkie ścieżki długości co najwyżej .

Poniżej zapis algorytmu dla sytuacji ścieżki długości :

 
 for  to  do
   zgadnij 
   if  i nie zachodzi  then
     return NIE
   end if
 end for
 if  then
   return TAK
 else
   return NIE 
 end if

To już koniec algorytmu. Krótka analiza wykazuje, że w trakcie jego działania musimy pamiętać jedynie skończoną liczbę wierzchołków i liczb wielkości co najwyżej zatem działa on w pamięci logarytmicznej.

Przejdźmy zatem do wykorzystania maszyny do udowodnienia tezy naszego twierdzenia. Weźmy język należący do , gdzie log , gdyż jest konstruowalna pamięciowo. Istnieje zatem maszyna niedeterministyczna akceptująca w pamięci niedeterministycznej. Musimy pokazać, że istnieje maszyna niedeterministyczna akceptująca również w pamięci . Bierzemy graf konfiguracji dla słowa wejściowego . Musimy stwierdzić, czy nie istnieje ścieżka od konfiguracji początkowej do akceptującej. Wtedy bowiem czyli ma zaakceptować .

Oznaczmy konfigurację akceptującą przez . Liczymy zatem zbiór dla grafu konfiguracji przy pomocy algorytmu z pierwszej części dowodu. Jeśli algorytm zakończy się wynikiem pozytywnym, to oznacza to, że jest policzone poprawnie. Jeśli zatem w trakcie przeglądania nie zakwalifikowaliśmy wierzchołka do żadnego ze zbiorów to znaczy, że nie jest on osiągalny.

W tej sytuacji maszyna może zaakceptować słowo , które nie należy do , a tym samym pokazujemy, że .

End of proof.gif

Klasy coNP i DP

Wprowadziliśmy już zarówno klasę jak i pojęcie dopełnień klas. Przyjrzyjmy się bliżej klasie . Klasa , jest to zbiór tych języków, dla których możemy łatwo weryfikować przynależność słów. Klasa natomiast, to zbiór tych języków, dla których możemy łatwo weryfikować, że słowo nie należy do języka.

Podobnie jak dla i twierdzenia Fagina, można scharakteryzować jako zbiór własności teoriografowych wyrażalnych w uniwersalnej logice drugiego rzędu.

Oto przykłady problemów z klasy :

Definicja 3.1 [Problem TAUTOLOGY:]

Wejście: formuła logiczna jak dla problemu SAT.
Wyjście: czy każde wartościowanie spełnia ?

Definicja 3.2 [Problem HAMILTON PATH COMPLEMENT:]

Wejście: graf nieskierowany .
Wyjście: czy nie zawiera ścieżki Hamiltona?

W powyższych problemach weryfikacja negatywna słowa wejściowego jest łatwa, bo opiera się na zgadnięciu wartościowania niespełniającego lub ścieżki Hamiltona.

Nietrudno udowodnić (patrz ćwiczenie końcowe), że są to problemy zupełne dla klasy . Nie jest to nic zaskakującego, bowiem równie prosto można udowodnić, że jeżeli jest -zupełny, to jego dopełnienie jest -zupełne.

Jak wiele pytań w teorii złożoności obliczeniowej również i to, czy pozostaje otwarte. Możemy jedynie stwierdzić, że jeżeli , to , gdyż jest zamknięta na dopełnienie. Jednak już implikacja w drugą stronę nie jest znana. Inna podobna implikacja to:

Ćwiczenie 3.3

Jeśli jest -zupełny i to .

Wskazówka
Rozwiązanie
Relacje pomiędzy klasami NP, coNP i DP.

Animacja Relacje pomiędzy klasami NP, coNP i DP przedstawia relacje pomiędzy poznanymi klasami i omawianą za chwilę klasą .

Oczywiście przyglądając się wszystkim takim rysunkom należy pamiętać, że mogą one w wielu miejscach kolapsować.

Klasa DP

Zastanówmy się nad następującym problemem:

Przykład 3.4 [Problem EXACT TSP]

Wejście: graf nieskierowany ważony i liczba
Wyjście: czy optymalna trasa komiwojażera dla ma wartość dokładnie ?

Jest to wersja dokładna znanego problemu optymalizacyjnego -- problemu komiwojażera. Wiemy że wersja decyzyjna TSP(D) jest -zupełna. Nietrudno pokazać również, że EXACT TSP i TSP(D) są wielomianowo równoważne (ćwiczenie końcowe), tzn., że jeśli jeden z nich ma rozwiązanie w czasie wielomianowym to drugi też. W tym rozdziale sklasyfikujemy złożoność EXACT TSP dokładniej przy pomocy klasy . Nie umiemy bowiem pokazać, że EXACT TSP należy do , wszak jak poświadczyć i szybko zweryfikować, że długość optymalnej trasy wynosi dokładnie ? Widzimy, że odpowiedź na to pytanie wymaga stwierdzenia, że trasa ma długość co najmniej i co najwyżej , co sugeruje pewne specyficzne połączenie problemu TSP(D) i jego dopełnienia.

Definicja 3.5 [Klasa DP]

Klasa DP to zbiór języków takich, że , gdzie natomiast .

Przy tak postawionej definicji EXACT TSP należy do . Jest on bowiem przecięciem języka TSP(D) i TSP(D) COMPLEMENT, tzn. koszt trasy wynosi dokładnie , gdy jest równy co najwyżej (to przynależność do TSP(D)) oraz co najmniej (to przynależność słowa do TSP(D) COMPLEMENT).

Klasa posiada problemy zupełne. Rozważmy problem następujący:

Przykład 3.6 [Problem SAT-UNSAT]

Wejście: formuły logiczne i jak dla SAT.
Wyjście: czy formuła jest spełnialna, natomiast niespełnialna?

Ćwiczenie 3.7

Udowodnij, że problem SAT-UNSAT jest -zupełny.

Wskazówka
Rozwiązanie

Również wspomniany na początku problem EXACT TSP jest -zupełny. Można rozważać także wiele innych wersji EXACT znanych problemów -zupełnych, które okazują się -zupełne.

Klasa zawiera także problemy -zupełne innego rodzaju:

Przykład 3.8 [Problem CRITICAL SAT]

Wejście: formuła logiczna jak dla SAT.
Wyjście: czy formuła jest nie spełnialna, natomiast usunięcie dowolnej klauzuli sprawia, że jest spełnialna?

Przykład 3.9 [Problem CRITICAL HAMILTON PATH

Wejście: graf nieskierowany
Wyjście: czy nie ma ścieżki Hamiltona, natomiast dodanie dowolnej krawędzi do powoduje, że już ją posiada?

Maszyny alternujące

W tym rozdziale przedstawimy ciekawe uogólnienie niedeterminizmu, zwane alternacją. Przypomnijmy, że maszyna niedeterministyczna akceptuje słowo, gdy na którejkolwiek ze ścieżek obliczeń trafi do stanu akceptującego.

Maszyna alternująca ma więcej możliwości. Każdy z jej stanów jest oznaczony poprzez "AND" lub "OR", które nazywamy odpowiednio stanami uniwersalnymi i egzystencjalnymi.

Gdy maszyna jest w stanie typu "OR", to dokonuje akceptacji gdy dowolna ze ścieżek obliczeń wychodzących z niego akceptuje słowo. Tak właśnie działają zawsze zwykłe maszyny niedeterministyczne.

Stany typu "AND" są rozszerzają tą funkcjonalność. Maszyna dokonuje akceptacji będąc w takim stanie, gdy każda ze ścieżek obliczeń wychodzących z tego stanu jest akceptująca.

Miarę złożoności czasowej i pamięciowej maszyn alternujących definiujemy zupełnie tak jak dla maszyn niedeterministycznych, tzn. funkcja jest miarą złożoności czasowej, gdy każda ze ścieżek obliczeń ma długość ograniczoną przez oraz złożoność pamięciową gdy na każdej ze ścieżek obliczeń maszyna zużywa co najwyżej pamięci.

Definicja 4.1 []

Poprzez oznaczamy zbiór języków takich, że są akceptowane przez alternującą maszynę Turinga o złożoności czasowej .

Definicja 4.2 []

Poprzez oznaczamy zbiór języków takich, że są akceptowane przez alternującą maszynę Turinga o złożoności pamięciowej .

Wprowadzamy też skróty dla najpopularniejszych klas:

  • Klasa , to klasa tych języków, które mogą być akceptowane w alternującym czasie wielomianowym,
  • Klasa (log), to klasa tych języków, które mogą być akceptowane w alternującej pamięci logarytmicznej,

Nietrudno się domyślić, że alternacja jest silniejsza niż niedeterminizm z definicji działania maszyn. Wiemy zatem, w szczególności, że zawiera w sobie . Poniższe ćwiczenie pokazuje, że o można powiedzieć więcej:

Ćwiczenie 4.3

Pokaż, że zawiera w sobie klasę .

Wskazówka
Rozwiązanie

To jednak nie wszystko co potrafi klasa . Znajdują się w niej języki, o których nie wiemy czy należą do lub .

Definicja 4.4 [Problem MIN-FORMULA]

Wejście: formuła logiczna jak dla problemu SAT.
Wyjście: czy jest minimalna, tzn. czy żadna krótsza formuła nie jest jej równoważna?

Ćwiczenie 4.5

Pokaż, że MIN-FORMULA należy do .

Wskazówka
Rozwiązanie

Teraz przedstawimy kilka relacji pomiędzy klasami obliczeń alternujących:

Twierdzenie 4.6

Następujące relacje są prawdziwe:

  1. Jeśli to ,
  2. Jeśli to ,
  3. Jeśli log to .
  4. Jeśli log to .
Zapis przebiegu obliczeń.

Dowód

Dowód własności od 1 do 3 jest przedmiotem ćwiczenia końcowego. Własność 4 wymaga trochę więcej pracy. Zauważmy, że musimy symulować maszynę działającą w czasie wykładniczym od dostępnej nam pamięci! Nie mamy zatem miejsca na potencjalną ilość pamięci, która może być potrzebna. Okazuje się jednak, że można sobie z tym poradzić:

Weźmy dowolną maszynę deterministyczną działającą w czasie . Będziemy symulować jej obliczenia od końca. Najpierw ustalamy, bez straty ogólności, że jest tylko jedna końcowa konfiguracja akceptująca, np. z całkowicie pustą taśmą , głowicą w komórce o numerze 1 i stanie .

Możemy przedstawić całe obliczenie w formie następującej tabelki przedstawiającej w rzędach kolejne zawartości taśmy, a w kolumnach czas. Dla uproszczenia przyjmijmy, że taśma jest jedna, i że pozycję głowicy notujemy specjalnym zapisem w tym miejscu pamięci, które ona odczytuje (podobnie notujemy stan). W ten sposób zawartość komórki zależy tylko od zawartości komórek , i (rysunek Zapis przebiegu obliczeń).

Teraz rozpoczynamy od dolnej części tabeli, której zawartość znamy i chcemy sprawdzić, czy obliczenie rozpoczęło się od pierwszego wiersza, który jest wejściem i którego zawartość też znamy.

Jeśli chcemy zweryfikować wartość komórki , to w trybie "OR" zgadujemy zawartość komórek , i . Następnie w trybie "AND" weryfikujemy ich poprawność i zgodność przejścia od , , do .

Ile pamięci jest nam potrzebne? Musimy pamiętać tylko wskaźniki do miejsc w wielkiej tabeli przedstawionej na rysunku, które sa rozmiaru log , co jest rzędu .

End of proof.gif

Dzięki wymienionym relacjom pomiędzy klasami alternującymi możemy udowodnić kilka dokładnych równości pomiędzy klasami, a to rzadka rzecz w teorii złożoności. Wiemy zatem, że:

  • AL=P,
  • APSPACE = EXP,
  • AP=PSPACE.

Hierarchia wielomianowa

W tej części zdefiniujemy całą hierarchię klas ponad znanymi nam już P i NP, która stanowi pewne uogólnienie problematyki spotkanej w klasie DP.

W poprzednich rozdziałach zdefiniowaliśmy pojęcie maszyny z wyrocznią na język oznaczanej przez . Przypomnijmy, że jest to zwykła maszyna z dodatkową możliwością zadania pytania postaci "czy ?" które kosztuje jedną jednostkę czasu. Rozszerzenie tego pojęcia na klasy jest naturalne. Poprzez oznaczamy zbiór tych języków, które mogą być rozstrzygane przez maszyny z klasy z wyrocznią na dowolny język z klasy .

Ta klasa okazuje się być mocniejsza od DP, bowiem w DP mogliśmy zadań pytanie tylko raz (dotyczące coNP, ale w sensie wyroczni działa to jak pytanie do NP), a tutaj dowolną liczbę razy i to na dodatek pytań adaptywnych, tzn. takich, które mogą zależeć od wyników odpowiedzi na poprzednie z nich. Kolejną interesującą klasą jest . Wszystkie te klasy dają nam coraz większe możliwości, lecz oczywiście nie wiadomo, czy są to ściśle większe klasy, choć panuje takie przekonanie (animacja Klasy relatywne).

Postępując w ten sposób Meyer i Stockmeyer w latach 70 zdefiniowali całą hierarchię klas:

Definicja 5.1 [Hierarchia wielomianowa]

Hierarchia wielomianowa, to ciąg klas indeksowany poprzez :

  • , dla ,
  • , dla ,
  • , dla .

Dodatkowo poprzez oznaczamy sumę wszystkich tych klas, czyli:
.

Ponieważ na poziomie zerowym wszystkie elementy hierarchii to , więc na poziomie pierwszym, ponieważ taka wyrocznia nic nie daje, otrzymujemy . Drugi poziom, to klasy . Warto zwrócić uwagę, że jest dopełnieniem na każdym poziomie wprost z definicji. Zawieranie się poszczególnych elementów na jednym poziomie obrazuje animacja Hierarchia wielomianowa.

Do tej pory często odwoływaliśmy się do odpowiedniości pomiędzy klasą a szczególnymi relacjami wielomianowo zrównoważonymi i rozstrzygalnymi. Przedstawimy teraz zgrabną charakteryzację klas z hierarchii wielomianowej przy pomocy podobnego kryterium:

Twierdzenie 5.2

Niech będzie językiem, . Język należy do wtedy i tylko wtedy, gdy istnieje wielomianowo zrównoważona i rozstrzygalna relacja (-argumentowa), taka, że dokładnie wtedy, gdy takie, że jest spełnione (-ty kwantyfikator jest uniwersalny, gdy jest parzyste, natomiast egzystencjalny, gdy jest nieparzyste).

Hierarchia wielomianowa jest strukturą dosyć wrażliwą na kolapsy, tzn. równości klas na pewnym poziomie. Okazuje się, że wtedy przenoszą się one automatycznie w górę:

Ćwiczenie 5.3

Pokaż, że jeżeli dla pewnego zachodzi to dla każdego zachodzi .

Wskazówka
Rozwiązanie

Zachodzi również podobny fakt. Otóż, jeśli (albo tylko ), to hierarchia kolapsuje już na pierwszym poziomie.

Można by się zastanowić, czy kolejne poziomy hierarchii wielomianowej są interesujące z punku widzenia problemów, które pozwalają one rozwiązać. Okazuje się, że na każdym poziomie hierarchii posiada ona problemy zupełne:

Definicja 5.4 [Problem QSAT ]

Wejście: formuła logiczna jak dla problemu SAT poprzedzona naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych: .
Wyjście: czy jest prawdziwa?

Twierdzenie 5.5

Problem jest -zupełny dla .

Jednak pytanie czy istnieje problem -zupełny (czyli zupełny dla całej hierarchii) jest otwarte i panuje przekonanie, że tak nie jest, gdyż:

Ćwiczenie 5.6

Pokaż, że jeśli istnieje problem -zupełny, to hierarchia zapada się na pewnym poziomie.

Wskazówka
Rozwiązanie

Jak silna jest cała hierarchia? Można łatwo zauważyć, że zawiera się ona w znanej już nam klasie , ze względu na fakt, że można łatwo rozstrzygać w wielomianowej pamięci relacje, charakteryzujące problemy z , które opisywaliśmy wcześniej.

Jak nietrudno się domyślić pytanie, czy jest otwarte. Bardzo interesujące jest jednak, że gdyby równość zachodziła, to ponieważ zawiera problemy zupełne, to również by je zawierała, stąd zapadła by się na pewnym skończonym poziomie. Stąd przekonanie, że zawiera się silnie w .

Na koniec ciekawy rezultat autorstwa Seinosuke Tody (laureata nagrody Goedl'a z roku 1998) związany z klasą . Pokazał on, że , czyli wyrocznia na klasę jest niesamowicie silna i pozwala pochłonąć tak misternie zbudowaną piramidę coraz silniejszych klas.

Ćwiczenia dodatkowe

Ćwiczenie 6.1

Pokaż, że problem TAUTOLOGY jest -zupełny.

Wskazówka
Rozwiązanie

Ćwiczenie 6.2

Udowodnij własności od 1 do 3 z twierdzenia 4.6.

  1. Jeśli to ,
  2. Jeśli to ,
  3. Jeśli log to .
Wskazówka
Rozwiązanie

Ćwiczenie 6.3

Udowodnij, że problemy TSP(D) i EXACT TSP są wielomianowo równoważne.

Wskazówka
Rozwiązanie

Testy końcowe