Złożoność obliczeniowa/Wykład 3: Klasy złożoności obliczeniowej

From Studia Informatyczne

Spis treści

Klasy złożoności czasowej i pamięciowej

W poprzednich modułach zostały wprowadzone maszyny Turinga oraz zdefiniowane pojęcie problemu obliczeniowego. Przypomnijmy, że problem obliczeniowy to dla nas język, czyli zbiór słów. Poznaliśmy także szczegółowo maszynę w wersji deterministycznej i niedeterministycznej oraz jej miarę złożoności czasowej i pamięciowej w każdej z wersji. W tym module zajmiemy się klasyfikacją języków przy pomocy maszyn. W naszych dalszych rozważaniach przyjmujemy model obliczeń w postaci maszyny Turinga o k taśmach.

Klasa złożoności obliczeniowej to zbiór problemów (języków) spełniających określone kryterium. Najbardziej podstawowe kryteria, tzn. czas i pamięć potrzebne do klasyfikacji języka dają nam podstawowe klasy złożoności:

Definicja 1.1 [\textsc{TIME}(f(n)) ]

Poprzez \textsc{TIME}(f(n)) oznaczamy zbiór języków L takich, że są akceptowane przez deterministyczną maszynę Turinga M o złożoności czasowej f(n).

Definicja 1.2 [\textsc{SPACE}(f(n))]

Poprzez \textsc{SPACE}(f(n)) oznaczamy zbiór języków L takich, że są akceptowane przez deterministyczną maszynę Turinga M o złożoności pamięciowej f(n).

Stosowne klasy można też zdefiniować dla niedeterministycznych maszyn:

Definicja 1.3 [\textsc{NTIME}(f(n))]

Poprzez \textsc{NTIME}(f(n)) oznaczamy zbiór języków L takich, że są akceptowane przez niedeterministyczną maszynę Turinga M o złożoności czasowej f(n).

Definicja 1.4 [\textsc{NSPACE}(f(n))]

Poprzez \textsc{NSPACE}(f(n)) oznaczamy zbiór języków L takich, że są akceptowane przez niedeterministyczną maszynę Turinga M o złożoności pamięciowej f(n).

Twierdzenia o liniowym przyspieszaniu i kompresji pamięci

Pierwsze dwa twierdzenia możemy nazwać "teoretycznymi podstawami" notacji O. Pokażemy bowiem, że w obu powyższych definicjach klas funkcja f(n) może być rozpatrywana z dokładnością do stałej, ze względu na specyfikę samego modelu obliczeń. Zostały one udowodnione w latach 60 przez pionierów badań nad klasami złożoności, laureatów nagrody Turinga z roku 1993, Jurisa Hartmanisa i Richarda Stearnsa.

Twierdzenie 2.1 [twierdzenie o liniowym przyspieszaniu]

Jeśli język L jest rozpoznawany przez maszynę M o złożoności czasowej f(n) to może być rozpoznany przez maszynę M' o złożoności czasowej f'(n)=\epsilon f(n) + (1+\epsilon) n, gdzie \epsilon>0.


Liniowe przyspieszanie


Obszar trzech

Dowód

Idea dowodu jest oparta na powiększeniu alfabetu maszyny, a tym samym wielkości "słowa" maszyny oraz liczby jej stanów. Odpowiada to w praktyce podniesieniu technologii wytwarzania komputerów. W animacji Liniowe przyspieszanie przedstawiono schematycznie zamianę 8 komórek pamięci na jedną większą nowej maszyny.

Nasza nowa maszyna o powiększonym alfabecie rozpoczyna działanie od skompresowania słowa wejściowego na drugiej taśmie i zamiany ról taśmy drugiej i wejściowej. Następnie głowica powraca na początek słowa i rozpoczyna obliczenia.

W każdym kroku obliczeń M' odczytuje bieżącą komórkę oraz dwie sąsiednie (na wszystkich taśmach), a następnie symuluje zachowanie M w obszarze tych trzech komórek dzięki zwiększonej stosownie liczbie stanów. Jako efekt następuje modyfikacja bieżącej komórki i komórek sąsiednich oraz stosowne przesunięcie głowicy.

Policzmy, czy taka symulacja rzeczywiście może być opłacalna. Załóżmy, że każda z komórek M' odpowiada c komórkom maszyny M, gdzie c - stopień kompresji, który ostatecznie ustalimy na końcu (będzie on oczywiście zależał od \epsilon i M). Alfabet nowej maszyny \Gamma' to alfabet starej maszyny \Gamma powiększony o symbole postaci \Gamma^c, które zapewniają nam zapis c symboli M w jednym symbolu M'.

W pierwszym etapie M' musi dokonać kompresji, czyli odczytać c symboli i zapisać 1 symbol skompresowany. Do tego celu wystarczy jej istnienie około |\Gamma^c| dodatkowych stanów. W ostatnim skompresowanym symbolu dokładamy symbole puste dla wyrównania. Czas działania tego etapu to około n+\lceil n/c \rceil (odczyt związany z kompresją + powrót).

W drugim etapie dokonujemy symulacji. Najpierw odczytujemy "obszar trzech" komórek na każdej taśmie co zajmuje 4 kroki M' (rysunek Obszar trzech).

Zapamiętujemy odczyt dzięki stosownemu powiększeniu liczby stanów M', które wykonujemy podobnie jak przy kompresji. Tym razem nowy zbiór stanów powiększamy o około \Gamma^{3c} (trzeba jeszcze pamiętać o zapamiętaniu pozycji każdej głowic wewnątrz obszarów, te szczegóły techniczne pomijamy). W tym momencie mamy pełną wiedzę kiedy maszyna M opuści "obszar trzech" i jak zostanie on zmodyfikowany. Oczywiście jeśli w tym czasie maszyna M kończy działanie, to tak robi również M'. W przeciwnym wypadku "obszar trzech" jest modyfikowany kolejnymi 4 ruchami M' i cykl rozpoczyna się od nowa. Wiemy jednak, że aby M opuściła obszar trzech komórek M' to musi wykonać przynajmniej c ruchów. Przyspieszyliśmy zatem działanie przynajmniej o czynnik c/8.

Podsumowując koszt czasowy to f'(n)=n+\lceil n/c \rceil+\lceil 8f(n)/c \rceil<(1+\epsilon)n + \epsilon f(n), jeśli c=\lceil 8/\epsilon \rceil, dla odpowiednio dużych n (dla małych n można stosownie rozbudować maszynę).

image:End_of_proof.gif

Twierdzenie nie ma zastosowania dla subliniowych funkcji złożoności, jednak maszyny, które nie czytają całego wejścia wydają się mało interesujące. W przypadku liniowej funkcji złożoności oznacza to, że stała może być dowolnie bliska 1.

Analogicznie twierdzenie zachodzi dla złożoności pamięciowej:

Ćwiczenie 2.2 [twierdzenie o liniowej kompresji pamięci]

Jeśli język L jest rozpoznawany przez maszynę M o złożoności pamięciowej f(n) to może być rozpoznany przez maszynę M' o złożoności pamięciowej f'(n)=\epsilon f(n), gdzie \epsilon>0.

Wskazówka

Skorzystaj z dowodu twierdzenia o liniowym przyspieszaniu.

Rozwiązanie

Dowód przebiega dokładnie tak samo jeśli chodzi o ideę. Wystarczy tylko dokonać obliczenia zużycia pamięci. Każda komórka nowej maszyny M' pamięta c symboli maszyny M, więc koszt pamięciowy to f'(n)=\lceil f(n)/c \rceil<\epsilon f(n), jeśli c=\lceil 1/\epsilon \rceil,

dla odpowiednio dużych n (ponownie dla małych n można stosownie rozbudować maszynę).

Na koniec ciekawostka dotycząca przyspieszania maszyn. Mając dany język L poszukujemy najszybszego algorytmu, który go akceptuje. Okazuje się, że jest język, dla którego nie istnieje algorytm asymptotycznie najszybszy! Autorem tego przeczącego intuicji twierdzenia jest Manuel Blum, laureat nagrody Turinga z roku 1995.

Twierdzenie 2.3 [twierdzenie Bluma o przyspieszaniu]

Istnieje język L, taki, że jeśli jest akceptowany przez maszynę Turinga o złożoności czasowej f(n), to jest również akceptowany, przez maszynę Turinga o złożoności czasowej \textnormal{log}(f(n)).

Relacje między klasami, twierdzenie Savitcha

Teraz jesteśmy gotowi do wprowadzenia podstawowych klas złożoności, w których funkcje są wyłącznie asymptotyczne:

  • Klasa \textnormal{P} = \bigcup_{j>0} \textnormal{TIME}(n^j), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wielomianowym,
  • Klasa \textnormal{NP} = \bigcup_{j>0} \textnormal{NTIME}(n^j), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wielomianowym,
  • Klasa \textnormal{EXP} = \bigcup_{j>0} \textnormal{TIME}(2^{n^j}), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,
  • Klasa \textnormal{NEXP} = \bigcup_{j>0} \textnormal{NTIME}(2^{n^j}), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.

dla klas pamięciowych:

  • Klasa \textnormal{L} = \textnormal{SPACE}(logn), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,
  • Klasa \textnormal{NL} = \textnormal{NSPACE}(logn), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
  • Klasa \textnormal{PSPACE} = \bigcup_{j>0} \textnormal{SPACE}(n^j), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wielomianowej,
  • Klasa \textnormal{NPSPACE} = \bigcup_{j>0} \textnormal{NSPACE}(n^j), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wielomianowej,
  • Klasa \textnormal{EXPSPACE} = \bigcup_{j>0} \textnormal{SPACE}(2^{n^j}), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,
  • Klasa \textnormal{NEXPSPACE} = \bigcup_{j>0} \textnormal{NSPACE}(2^{n^j}), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wykładniczej.

Teraz zajmiemy się relacjami pomiędzy poszczególnymi klasami złożoności. Najbardziej podstawowe zależności, łączące czas, pamięć i niedeterminizm to:

  • \textnormal{TIME}(f(n))\subseteq\textnormal{NTIME}(f(n)), gdyż z definicji, każda maszyna deterministyczna jest maszyną niedeterministyczną,
  • \textnormal{SPACE}(f(n))\subseteq\textnormal{NSPACE}(f(n)), jak wyżej,
  • \textnormal{TIME}(f(n))\subseteq\textnormal{SPACE}(f(n)), gdyż maszyna nie może zapisać więcej komórek niż wynosi jej czas działania,
  • \textnormal{NTIME}(f(n))\subseteq\textnormal{NSPACE}(f(n)), jak wyżej,
  • \textnormal{NTIME}(f(n))\subseteq\textnormal{TIME}(c^{f(n)}), na podstawie twierdzenia z modułu pierwszego o symulacji

maszyny niedeterministycznej przez maszynę deterministyczną.

Aby powiedzieć więcej o relacjach pomiędzy klasami musimy narzucić pewne rozsądne ograniczenie na funkcję złożoności f(n). Powiemy, że f(n) jest konstruowalna pamięciowo, gdy f(n)\geqslant \textnormal{log}n oraz istnieje deterministyczna maszyna Turinga, która mając na wejściu n zapisane unarnie potrafi zużyć dokładnie f(n) komórek pamięci i zatrzymać się.

Zawężamy się w ten sposób do funkcji f(n)\geqslant \textnormal{log}n, lecz mniejszych złożoności nie będziemy tutaj rozważać (mimo, iż można). Warto dodać, że jeśli maszyna działa w pamięci o(\textnormal{log log}n) to działa w pamięci stałej.

Okazuje się, że większość interesujących funkcji spełnia tą własność. Jest to także własność zamknięta ze względu na dodawanie, mnożenie i potęgowanie.

Ćwiczenie 3.1

Pokaż, że funkcje \lceil \textnormal{log}n \rceil, n^k, 2^{n}konstruowalne pamięciowo.

Wskazówka

Zastosuj definicję i skonstruuj stosowne maszyny.

Rozwiązanie

Dowód konstruowalności pamięciowej funkcji

\lceil \textnormal{log}n \rceil opieramy na implementacji klasycznego licznika binarnego. Długość zapisu liczby binarnej n to właśnie \lceil \textnormal{log}n \rceil. Dla funkcji wielomianowej wykonujemy serię prostych działań arytmetycznych polegających na mnożeniu i dodawaniu liczb naturalnych zapisanych binarnie. W przypadku funkcji wykładniczej wystarczy zaprogramować maszynę, aby n razy dokonała podwojenia liczby zużytych komórek.

Poniżej przedstawiamy twierdzenie, które zachodzi, jeśli nie narzucimy dodatkowego warunku na funkcję złożoności. Wprowadzając go, chcemy uniknąć podobnych sytuacji:

Twierdzenie 3.2 [twierdzenie o luce]

Istnieje funkcja rekurencyjna f(n) taka, że \textnormal{TIME}(f(n))=\textnormal{TIME}(2^{f(n)}).

Dowód

Przedstawimy bardzo specyficzną definicję funkcji f(n), dla której każda maszyna na słowie o długości n działa w czasie co najwyżej f(n) lub działa przynajmniej 2^{f(n)}+1 kroków lub pętli się. W ten sposób pokażemy stosowną równość klas. Dowód opiera się na bardzo użytecznej i często stosowanej technice przekątniowej.

Będziemy rozważać wszystkie możliwe maszyny w pewnej ustalonej kolejności M_1, M_2, \ldots wynikającej np. z leksykograficznego porządku na ich kodach zdefiniowanych w module pierwszym. Ponieważ każda maszyna może być opisana skończonym słowem, więc wygenerowanie takiego ciągu wszystkich maszyn jest wykonalne.

Zdefiniujmy relację binarną P(i,k) w ten sposób, by była spełniona, gdy każda maszyna od 1 do i działając na dowolnym słowie o długości i działa w czasie co najwyżej k lub działa przynajmniej 2^k+1 kroków lub pętli się. Tą relację jesteśmy w stanie obliczyć poprzez stosowną symulację maszyn M_1, \ldots, M_i na wszystkich słowach długości i przez co najwyżej 2^k+1 kroków (oczywiście jest to dosyć czasochłonne), tym samym ewentualne pętlenie się maszyn nie stanowi przeszkody.

Teraz jesteśmy gotowi do zdefiniowania f(n). Ustalmy n. Zauważmy, że P(n,k) musi być prawdziwa dla pewnego k. Dzieje się tak dlatego, gdyż wraz ze wzrostem k zmieniamy zabroniony obszar czasu działania maszyn od 1 do n. Liczba słów które testujemy jest jednak ograniczona - są to wszystkie słowa o długości dokładnie n dla tych maszyn. Aby P(n,k) nie było prawdą to czas działania maszyny na słowie musi trafić do obszaru zabronionego, co wobec ustalonej liczby słów i zwiększania k spowoduje, że P(n,k) w końcu będzie prawdą. Definiujemy wartość f(n) jako najmniejsze takie k.

Weźmy dowolny język L\in\textnormal{TIME}(2^{f(n)}). Jest on akceptowany przez maszynę, którą oznaczmy M_j (w naszym porządku ustalonym w pierwszej części). Maszyna ma złożoność 2^{f(n)}. Weźmy dowolne słowo o długości l\geqslant j. Wiemy, że P(l,f(l)) jest spełnione, a tym samym maszyna M_j działa w czasie co najwyżej f(l) (bo więcej niż 2^{f(l)} nie może z definicji klasy). Zatem L\in\textnormal{TIME}(f(n)).

Pominęliśmy działanie na słowach krótszych niż j, jednakże jest to stała liczba słów, które łatwo zaakceptować w czasie rzędu ich długości po prostu wbudowując ich przynależność do L w maszynę.

image:End_of_proof.gif

W literaturze rozważa się wiele wersji "normujących" dopuszczalne funkcji złożoności, np. właściwie funkcje złożoności lub funkcje uczciwe. Różnice między nimi są dosyć techniczne. Przyjmijmy zatem, że funkcje złożoności f(n) są konstruowalne pamięciowo.

Przeanalizujmy teraz możliwe konfiguracje maszyny Turinga M, które tworzą tzw. graf przejść maszyny:

Ćwiczenie 3.3

W jak wielu konfiguracjach może znaleźć się maszyna Turinga o złożoności pamięciowej f(n) (konstruowalnej pamięciowo) przeprowadzając obliczenie na słowie o długości n?

Wskazówka

Policz liczbę stanów maszyny, położeń głowic i zawartości taśm.

Rozwiązanie

Liczba możliwych konfiguracji to oczywiście iloczyn:

  • liczby stanów |Q|,
  • położeń głowic na wszystkich taśmach, jest rzędu f(n)^k jednak nie mniej niż n (dokładny wynik zależy od przyjętych wyróżnień taśmy wejściowej i wyjściowej),
  • zawartości taśm, czyli |\Gamma|^{k f(n)}.

Razem możemy to ograniczyć przez c^{f(n)}, dla pewnego c zależnego tylko od maszyny oraz korzystając z założenia, że f(n)\geqslant \textnormal{log}n, gdyż jest konstruowalna pamięciowo.

Teraz jesteśmy gotowi do wypowiedzenia kolejnych interesujących relacji pomiędzy wprowadzonymi klasami:

  • \textnormal{SPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)}), ze względu na fakt, iż liczba możliwych konfiguracji maszyny o złożoności pamięciowej f(n),

co pokazaliśmy przed chwilą wynosi c^{f(n)}, zatem maszyna, która się nie pętli może zostać zasymulowana przez maszynę działającą co najwyżej tak długo. W przeciwnym wypadku wpadła by w nieskończoną pętlę.

  • \textnormal{NTIME}(f(n))\subseteq\textnormal{SPACE}(f(n)), gdyż maszyna deterministyczna może zasymulować działanie maszyny niedeterministycznej.

Wystarczy wygenerować po kolei każdy z ciągów f(n) niedeterministycznych wyborów (tu korzystamy z pamięciowej konstruowalności), których musi ona dokonać w trakcie obliczeń. Następnie dokonujemy już deterministycznej symulacji obliczeń przez f(n) kroków. Wszystkie te operacje można dokonać w dostępnej pamięci f(n), gdyż każdy z ciągów niedeterministycznych wyborów możemy symulować w tej samej pamięci,

  • \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)}), ponownie opierając się na symulacji maszyny.

Jak poprzednio liczba wszystkich konfiguracji wynosi c^{f(n)}, jednak tym razem przejścia pomiędzy poszczególnymi konfiguracjami tworzą graf. Wystarczy jednak obliczyć, czy istnieje ścieżka od konfiguracji początkowej do konfiguracji końcowej, co może być obliczone w czasie wielomianowym ze względu na rozmiar grafu, a zatem w czasie asymptotycznym c^{f(n)}.

Dzięki powyższym relacjom możemy wypisać kilka podstawowych zależności pomiędzy wprowadzonymi klasami:

Ćwiczenie 3.4

Uzasadnij każdą z poniższych relacji:

  • \textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}
  • \textnormal{PSPACE}\subseteq\textnormal{NPSPACE}\subseteq\textnormal{EXP}\subseteq\textnormal{NEXP}\subseteq\textnormal{EXPSPACE}\subseteq\textnormal{NEXPSPACE}

Wskazówka

Skorzystaj z poznanych już własności klas oraz własności funkcji logarytmicznej, wielomianowej i wykładniczej.

Rozwiązanie

Wszystkie zawierania pochodzą z wypisanych wcześniej ogólnych zależności. Nietrywialne, to:

  • \textnormal{NL}\subseteq\textnormal{P}, korzystamy z faktu, że \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)}), w tym wypadku mamy bowiem c^{\textnormal{log}n}=n^k,
  • \textnormal{NPSPACE}\subseteq\textnormal{EXP}, również korzystamy z faktu, że \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)}), w tym wypadku mamy bowiem c^{n^k}=2^{n^{k'}}.

Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją w animacji Relacje pomiędzy podstawowymi klasami.



Relacje pomiędzy podstawowymi klasami
\textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}

W następnej części z twierdzenia o hierarchii pamięciowej dowiemy się, że L\varsubsetneq \textnormal{PSPACE}. Tym samym wiemy, że pierwszy i ostatni element są różne. Jedną z najbardziej fascynujących rzeczy w teorii złożoności jest fakt, że przynajmniej jedno z czterech powyższych zawierań musi być ścisłe, jednakże o żadnym z nich tego nie wiadomo! Najsłynniejszy fragment to oczywiście pytanie o zawieranie pomiędzy P i NP.

Ostatnią i najciekawszą relacją pomiędzy klasami jest ta odkryta przez Savitcha, mówiąca o niewielkiej przewadze niedeterministycznej złożoności pamięciowej. Przypomnijmy, że do tej pory wiemy poprzez połączenie dwóch wymienionych własności, że \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(c^{f(n)}). Okazuje się, że zachodzi twierdzenie dużo silniejsze:

Twierdzenie 3.5 [twierdzenie Savitcha]

Jeśli f(n) jest konstruowalna pamięciowo, to \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(f^2(n)).



Wierzchołek pośredni

Dowód

Wspominaliśmy już o tym, że kluczowym elementem symulacji maszyny niedeterministycznej jest sprawdzanie czy istnieje ścieżka od konfiguracji początkowej do końcowej maszyny. Problem sprawdzania czy dwa wierzchołki w grafie są połączone ścieżką jest znany jako REACHABILITY. Savitch udowodnił, że REACHABILITY należy do SPACE(\textnormal{log}^2n), gdzie n to rozmiar grafu. W naszym wypadku rozmiar grafu to liczba konfiguracji, czyli c^{f(n)}, zatem REACHABILITY wymaga czasu \textnormal{log}^2(c^{f(n)})=O(f(n))^2, co da nam tezę. Od tej pory przyjmijmy, że graf ma n wierzchołków.

Wprowadźmy pomocniczą funkcję \textnormal{PATH}(x,y,i) która ma zwrócić 1, gdy istnieje ścieżka od x do y w grafie zawierająca co najwyżej i wierzchołków. Nasze pytanie możemy przeformułować jako PATH(b,e,n), gdzie b to stan początkowy, e końcowy, a n to maksymalna długość ścieżki w grafie konfiguracji, czyli liczba wszystkich wierzchołków.

Obliczymy \textnormal{PATH}(x,y,i) w sposób rekurencyjny. Jeśli i=1 to sprawdzamy bezpośrednie przejście od konfiguracji x do y. W przeciwnym wypadku najpierw wybieramy dowolny wierzchołek jako kandydata na wierzchołek pośredni na ścieżce pomiędzy x i y, który oznaczmy przez t (rysunek Wierzchołek pośredni).

Potem wywołujemy rekurencyjnie \textnormal{PATH}(x,t,i/2) oraz \textnormal{PATH}(t,y,i/2). Jeśli obie ścieżki istnieją to zwracamy 1, w przeciwnym wypadku próbujemy kolejny wierzchołek t. Nie musimy się martwić o czas, tylko pamięć, więc policzmy ile jest nam potrzebne.

Głębokość rekurencji wyniesie \textnormal{log}n, ze względu na fakt iż na każdym poziomie zmniejszamy długość o czynnik 2. Aby zapamiętać wywołanie rekurencyjne (stos rekurencyjny) potrzebujemy pamiętać x, y, bieżące t oraz i. Wszystkie te liczby w zapisie binarnym potrzebują \textnormal{log}n pamięci. Razem potrzebujemy O(\textnormal{log}^2n) pamięci.

image:End_of_proof.gif

Na podstawie twierdzenia Savitcha wiemy, że niektóre z poznanych klas są sobie równe:

  • PSPACE = NPSPACE,
  • EXPSPACE = NEXPSPACE.

czyli, że niedeterminizm w złożoności pamięciowej dla większych funkcji nic nie daje. Dla klas złożoności czasowej takiej wiedzy nie posiadamy!

Dopełnienia klas

W tym rozdziale przyjrzymy się dopełnieniom języków i klas. Jeśli L jest językiem to przez \overline{L}=\sum^*\setminus L oznaczamy jego dopełnienie. W przypadku problemów decyzyjnych dopełnienie (ang. COMPLEMENT) to problem decyzyjny, w którym odpowiedzi są odwrócone.

Jeśli rozważymy SAT, w którym pytamy czy formuła może zostać spełniona, to jego dopełnienie to SAT COMPLEMENT. Jest to problem bardzo blisko spokrewniony z TAUTOLOGY, w którym pytamy czy każde wartościowanie formuły \phi ją spełnia. SAT COMPLEMENT to pytanie, czy formuła nie ma wartościowań spełniających, co jest równoważne temu, że \neg \phi jest formułą zawsze spełnioną, czyli jest tautologią logiczną.

COMPLEMENT nie jest ściśle dopełnieniem języka, gdyż \overline{SAT} zawiera także wszystkie słowa, które nie są poprawnymi opisami formuł. Te słowa nie stanowią jednak problemu w rozpoznawaniu.

Zdefiniujemy teraz pojęcie dopełnienia klasy złożoności. Przypomnijmy, że klasy złożoności składają się z języków. Jeśli C jest dowolną klasą złożoności to przez \textnormal{co}C oznaczamy jej dopełnienie, które jest złożone z dopełnień języków z klasy C.

Zauważmy od razu, że jeśli C jest klasą deterministyczną, to \textnormal{co}C=C ze względu na fakt, iż maszyna deterministyczna, która akceptuje język L\in C po zamianie rolami stanu akceptującego i odrzucającego stanie się maszyną akceptującą język \overline{L}.

W module dotyczącym pamięci logarytmicznej dowiemy się, że klasy niedeterministycznej złożoności pamięciowej również zamknięte są na dopełnienia, natomiast w przypadku klas niedeterministycznych złożoności czasowej nie wiemy jakie są relacje pomiędzy nimi i jest to problem otwarty.

Twierdzenia o hierarchii czasowej i pamięciowej

W tej części poznamy dwa ważne twierdzenia, które wprowadzają pojęcia hierarchii czasowej i pamięciowej, tzn. pokażemy, że większe złożoności rzeczywiście istotnie pozwalają akceptować więcej języków.

Twierdzenie 3.6 [twierdzenie o hierarchii pamięciowej]

Jeśli f(n) jest konstruowalna pamięciowo oraz g(n) \in o(f(n)) (czyli rośnie asymptotycznie wolniej) to \textnormal{SPACE}(g(n)) \subsetneq  \textnormal{SPACE}(f(n)).



Maszyna przekątniowa

Dowód

Pokażemy, że istnieje język L\in\textnormal{SPACE}(f(n)) taki, że L\notin\textnormal{SPACE}(g(n)). Aby zapewnić pierwszy warunek, skonstruujemy maszynę M dla L, która ma złożoność pamięciową f(n). Drugi warunek zapewnimy pokazując, że żadna z maszyn o złożoności pamięciowej g(n) nie akceptuje L.

Maszyna M działa następująco. Gdy na wejściu dostanie słowo o długości n to w pierwszym etapie oznakowuje f(n) komórek pamięci na każdej z taśm. Będziemy bowiem symulować inne maszyny i chcemy się upewnić, że nie zużywają one więcej niż f(n) pamięci. Możemy to zrobić dzięki konstruowalności pamięciowej f(n).

Teraz następuje część przekątniowa (rysunek Maszyna przekątniowa).

W drugim etapie maszyna M interpretuje słowo x z wejścia jako kod maszyny M'. Maszyna M odrzuca słowa, które nie są poprawnymi kodami. Gdy kod jest poprawny, to rozpoczyna się symulacja M' na tym samym słowie x. Jeśli symulacja przekroczy oznakowaną pamięć f(n) to maszyna M również odrzuca słowo x. Jeśli maszyna M' zaakceptuje x to maszyna M odrzuca x i jeśli M' odrzuca x to M je akceptuje.

Maszyna M ma złożoność pamięciową f(n), więc L=L(M)\in\textnormal{SPACE}(f(n)). Zastanówmy się, czy język L należy do klasy \textnormal{SPACE}(g(n)). Wtedy jest akceptowany przez maszynę M' o złożoności g(n). Zastanówmy się co dzieje się, gdy M' dostanie na wejściu swój kod \textnormal{<}M'\textnormal{>}. Ponieważ M' akceptuje język w czasie g(n), więc i na słowie x działa w takim czasie. Załóżmy, że odrzuca x. Wtedy maszyna M zaakceptuje x, gdyż symulacja którą ona przeprowadza, tzn. działanie M' na x może zostać przeprowadzona, jako że g(n) jest asymptotycznie mniejsze niż f(n) (pomijamy szczegóły techniczne, które pojawią się dla małych n). Analogicznie, gdy M' akceptuje x to M je odrzuca, czyli M' nie może akceptować L, gdyż myli się na x=M'.

Otrzymujemy sprzeczność, stąd L \notin \textnormal{SPACE}(g(n)).

image:End_of_proof.gif

A teraz pora na analogiczne twierdzenie o hierarchii czasowej. Potrzebne jest nam do niego dodatkowe ograniczenie na funkcję złożoności. Powiemy, że f(n) jest konstruowalna czasowo, gdy f(n)\geqslant n\textnormal{log}n oraz istnieje deterministyczna maszyna Turinga, która mając na wejściu n zapisane unarnie potrafi działać przez dokładnie f(n) kroków i zatrzymać się. Również w tym wypadku większość znanych funkcji jest konstruowalna.

Twierdzenie 3.7 [twierdzenie o hierarchii czasowej]

Jeśli f(n) jest konstruowalna czasowo oraz g(n) \in o(f(n)/\textnormal{log}f(n)) to \textnormal{TIME}(g(n)) \subsetneq  \textnormal{TIME}(f(n)).

Dowód jest przedmiotem ćwiczenia końcowego. Teraz możemy wyciągnąć kilka ważnych wniosków o silnym zawieraniu się klas złożoności:

  • \textnormal{SPACE}(n^{\epsilon_1})\subsetneq\textnormal{SPACE}(n^{\epsilon_2}), gdy 0\leqslant\epsilon_1 < \epsilon_2, z własności funkcji wielomianowej,
  • \textnormal{TIME}(n^{\epsilon_1})\subsetneq\textnormal{TIME}(n^{\epsilon_2}), gdy 1\leqslant\epsilon_1 < \epsilon_2, jak wyżej,
  • \textnormal{L}\subsetneq\textnormal{PSPACE}, gdyż logarytm rośnie wolniej niż funkcja wielomianowa,
  • \textnormal{P}\subsetneq\textnormal{EXP}, korzystamy z własności, że każdy wielomian rośnie wolniej niż funkcja subwykładnicza n^{\textnormal{log}n} a ta z kolei rośnie wolniej, niż każda funkcja wykładnicza.
  • \textnormal{PSPACE}\subsetneq\textnormal{EXPSPACE}, jak wyżej.

Widzimy zatem, że klasa P, pojmowana jako zbiór praktycznie rozwiązywalnych problemów również podlega hierarchii. Istnieją w niej języki które są akceptowane w czasie n^{10000} natomiast w n^{9999} już nie. To sprawia, że należy patrzeć na praktyczność klasy P z pewną ostrożnością.

Ćwiczenia dodatkowe

Ćwiczenie 4.1

Udowodnij twierdzenie o hierarchii czasowej: Jeśli f(n) jest konstruowalna czasowo oraz g(n) \in o(f(n)/\textnormal{log}f(n)) to \textnormal{TIME}(g(n)) \subsetneq  \textnormal{TIME}(f(n)).

Wskazówka

Przeprowadź rozumowanie podobne jak w dowodzie twierdzenia o hierarchii pamięciowej.

Rozwiązanie

Jak w dowodzie twierdzenia o hierarchii pamięciowej skonstruujemy maszynę M, której język L=L(M)

należy do \textnormal{TIME}(f(n)), ale nie należy do \textnormal{TIME}(g(n)).

Konstruujemy M tak, że bierze x z wejścia i traktuje jako kod maszyny. Następnie

symuluje jej działanie nie jak poprzednio w pamięci f(n) lecz w czasie f(n). Aby jednak dokonać takiej symulacji maszyna M musi zliczać liczbę wykonanych kroków symulacji. Symulacja każdego kroku zajmuje teraz \textnormal{log}(f(n)) potrzebnych do zaimplementowania licznika. Stąd można zasymulować każdą maszynę o złożoności asymptotycznie mniejszej niż f(n)\textnormal{log}f(n) a tym samym wykazać przy pomocy przekątniowej metody, że język M jest różny od języka każdej z tych maszyn.

Ćwiczenie 4.2

Udowodnij następujące fakty:

  • \textnormal{NTIME}(n)\subsetneq \textnormal{PSPACE}
  • \textnormal{TIME}(2^n) = \textnormal{TIME}(2^{n+1})
  • \textnormal{TIME}(2^n)\subsetneq \textnormal{TIME}(2^{2n})

Wskazówka

Użyj poznanych twierdzeń o przyspieszaniu i hierarchii.

Rozwiązanie

Ad. 1: Wiemy, że \textnormal{NTIME}(n) \subseteq \textnormal{SPACE}(n). Następnie na podstawie twierdzenia o hierarchii pamięciowej \textnormal{SPACE}(n) \subsetneq \textnormal{PSPACE}, co kończy dowód.

Ad. 2:

Oczywiście \textnormal{TIME}(2^n) \subseteq \textnormal{TIME}(2^{n+1}). Weźmy teraz dowolny język L należący do klasy \textnormal{TIME}(2^{n+1}). Istnieje zatem maszyna działająca w czasie 2^{n+1}. Z twierdzenia o przyspieszaniu wiemy, że istnieje inna maszyna M' akceptująca ten sam język L, ale działająca w czasie 2^{n+1}/4, gdy zastosujemy \epsilon = 1/4 (czynnik liniowy obok funkcji wykładniczej jest nieistotny). Lecz 2^{n+1}/4=2^n/2, a zatem L należy do \textnormal{TIME}(2^n) co dowodzi tezy.

Ad. 3:

Zastosujemy twierdzenie o hierarchii czasowej dla funkcji f(n)=2^{2n} oraz g(n)=2^n. Musimy tylko wykazać, że funkcje spełniają założenia twierdzenia. Mamy jednak f(n)/\textnormal{log}(f(n))=2^{2n}/2n=(2^n/2n)2^n zatem dominuje asymptotycznie 2^n co kończy dowód.

Testy końcowe