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

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 [${\text{TIME}}(f(n))$ ]

Poprzez ${\text{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 [${\text{SPACE}}(f(n))$]

Poprzez ${\text{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 [${\text{NTIME}}(f(n))$]

Poprzez ${\text{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 [${\text{NSPACE}}(f(n))$]

Poprzez ${\text{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ę).

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 ${\text{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 ${\text{P}}=\bigcup _{j>0}{\text{TIME}}(n^{j})$, to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wielomianowym,
• Klasa ${\text{NP}}=\bigcup _{j>0}{\text{NTIME}}(n^{j})$, to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wielomianowym,
• Klasa ${\text{EXP}}=\bigcup _{j>0}{\text{TIME}}(2^{n^{j}})$, to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,
• Klasa ${\text{NEXP}}=\bigcup _{j>0}{\text{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 ${\text{L}}={\text{SPACE}}($log$n)$, to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,
• Klasa ${\text{NL}}={\text{NSPACE}}($log$n)$, to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,
• Klasa ${\text{PSPACE}}=\bigcup _{j>0}{\text{SPACE}}(n^{j})$, to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wielomianowej,
• Klasa ${\text{NPSPACE}}=\bigcup _{j>0}{\text{NSPACE}}(n^{j})$, to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wielomianowej,
• Klasa ${\text{EXPSPACE}}=\bigcup _{j>0}{\text{SPACE}}(2^{n^{j}})$, to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,
• Klasa ${\text{NEXPSPACE}}=\bigcup _{j>0}{\text{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:

• ${\text{TIME}}(f(n))\subseteq {\text{NTIME}}(f(n))$, gdyż z definicji, każda maszyna deterministyczna jest maszyną niedeterministyczną,
• ${\text{SPACE}}(f(n))\subseteq {\text{NSPACE}}(f(n))$, jak wyżej,
• ${\text{TIME}}(f(n))\subseteq {\text{SPACE}}(f(n))$, gdyż maszyna nie może zapisać więcej komórek niż wynosi jej czas działania,
• ${\text{NTIME}}(f(n))\subseteq {\text{NSPACE}}(f(n))$, jak wyżej,
• ${\text{NTIME}}(f(n))\subseteq {\text{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 {\text{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 {\text{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({\text{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 {\text{log}}n\rceil$, $n^{k}$, $2^{n}$ są konstruowalne pamięciowo.

Wskazówka

Zastosuj definicję i skonstruuj stosowne maszyny.

Rozwiązanie

Dowód konstruowalności pamięciowej funkcji

$\lceil {\text{log}}n\rceil$ opieramy na implementacji klasycznego licznika binarnego. Długość zapisu liczby binarnej $n$ to właśnie $\lceil {\text{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 ${\text{TIME}}(f(n))={\text{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 {\text{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 {\text{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ę.

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 |^{kf(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 {\text{log}}n$, gdyż jest konstruowalna pamięciowo.

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

• ${\text{SPACE}}(f(n))\subseteq {\text{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ę.

• ${\text{NTIME}}(f(n))\subseteq {\text{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,

• ${\text{NSPACE}}(f(n))\subseteq {\text{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:

• ${\text{L}}\subseteq {\text{NL}}\subseteq {\text{P}}\subseteq {\text{NP}}\subseteq {\text{PSPACE}}$
• ${\text{PSPACE}}\subseteq {\text{NPSPACE}}\subseteq {\text{EXP}}\subseteq {\text{NEXP}}\subseteq {\text{EXPSPACE}}\subseteq {\text{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:

• ${\text{NL}}\subseteq {\text{P}}$, korzystamy z faktu, że ${\text{NSPACE}}(f(n))\subseteq {\text{TIME}}(c^{f(n)})$, w tym wypadku mamy bowiem $c^{{\text{log}}n}=n^{k}$,
• ${\text{NPSPACE}}\subseteq {\text{EXP}}$, również korzystamy z faktu, że ${\text{NSPACE}}(f(n))\subseteq {\text{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.

|size=small</flashwrap><div.thumbcaption style="width:250;">Relacje pomiędzy podstawowymi klasami

${\text{L}}\subseteq {\text{NL}}\subseteq {\text{P}}\subseteq {\text{NP}}\subseteq {\text{PSPACE}}$

W następnej części z twierdzenia o hierarchii pamięciowej dowiemy się, że $L\varsubsetneq {\text{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 ${\text{NSPACE}}(f(n))\subseteq {\text{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 ${\text{NSPACE}}(f(n))\subseteq {\text{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$(${\text{log}}^{2}n$), gdzie $n$ to rozmiar grafu. W naszym wypadku rozmiar grafu to liczba konfiguracji, czyli $c^{f(n)}$, zatem REACHABILITY wymaga czasu ${\text{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ę ${\text{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 ${\text{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 ${\text{PATH}}(x,t,i/2)$ oraz ${\text{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 ${\text{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ą ${\text{log}}n$ pamięci. Razem potrzebujemy $O({\text{log}}^{2}n)$ pamięci.

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 ${\text{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 ${\text{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 ${\text{SPACE}}(g(n))\subsetneq {\text{SPACE}}(f(n))$.

Maszyna przekątniowa

Dowód

Pokażemy, że istnieje język $L\in {\text{SPACE}}(f(n))$ taki, że $L\notin {\text{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 {\text{SPACE}}(f(n))$. Zastanówmy się, czy język $L$ należy do klasy ${\text{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 $<M'>$. 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 {\text{SPACE}}(g(n))$.

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{\text{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)/{\text{log}}f(n))$ to ${\text{TIME}}(g(n))\subsetneq {\text{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:

• ${\text{SPACE}}(n^{\epsilon _{1}})\subsetneq {\text{SPACE}}(n^{\epsilon _{2}})$, gdy $0\leqslant \epsilon _{1}<\epsilon _{2}$, z własności funkcji wielomianowej,
• ${\text{TIME}}(n^{\epsilon _{1}})\subsetneq {\text{TIME}}(n^{\epsilon _{2}})$, gdy $1\leqslant \epsilon _{1}<\epsilon _{2}$, jak wyżej,
• ${\text{L}}\subsetneq {\text{PSPACE}}$, gdyż logarytm rośnie wolniej niż funkcja wielomianowa,
• ${\text{P}}\subsetneq {\text{EXP}}$, korzystamy z własności, że każdy wielomian rośnie wolniej niż funkcja subwykładnicza $n^{{\text{log}}n}$ a ta z kolei rośnie wolniej, niż każda funkcja wykładnicza.
• ${\text{PSPACE}}\subsetneq {\text{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)/{\text{log}}f(n))$ to ${\text{TIME}}(g(n))\subsetneq {\text{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 ${\text{TIME}}(f(n))$, ale nie należy do ${\text{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 ${\text{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){\text{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:

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

Wskazówka

Użyj poznanych twierdzeń o przyspieszaniu i hierarchii.

Rozwiązanie

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

Ad. 2: Oczywiście ${\text{TIME}}(2^{n})\subseteq {\text{TIME}}(2^{n+1})$. Weźmy teraz dowolny język $L$ należący do klasy ${\text{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 ${\text{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)/{\text{log}}(f(n))=2^{2n}/2n=(2^{n}/2n)2^{n}$ zatem dominuje asymptotycznie $2^{n}$ co kończy dowód.