Złożoność obliczeniowa/Wykałd 3: Klasy złożoności obliczeniowej

Przedmiot & Złożoność obliczeniowa
Moduł & 3
Tytuł & Klasy złożoności obliczeniowej
Opracowanie & Przemysław Broniek
{ Syllabus} Klasy złożoności obliczeniowej

• klasy złożoności czasowej i pamięciowej,

• twierdzenia o liniowym przyspieszaniu i kompresji pamięci,

• relacje między klasami, twierdzenie Savitcha i dopełnienia klas,

• twierdzenia o hierarchii czasowej i pamięciowej.

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 [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \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 [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \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 [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \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 [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \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 [Uzupelnij]

(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^{\prime }$ o złożoności czasowej $f^{\prime }(n)=ϵf(n)+(1+ϵ)n$, gdzie $ϵ>0$.

Dowód [Uzupelnij]

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. Na rysunku przedstawiono schematycznie zamianę 8 komórek pamięci na jedną większą nowej maszyny:

{ZO-3-1-rys}{Liniowe przyspieszanie}

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^{\prime }$ 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^{\prime }$ 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 $ϵ$ i $M$). Alfabet nowej maszyny ${\mathrm{\Gamma }}^{\prime }$ to alfabet starej maszyny $\mathrm{\Gamma }$ powiększony o symbole postaci ${\mathrm{\Gamma }}^c$, które zapewniają nam zapis $c$ symboli $M$ w jednym symbolu $M^{\prime }$.

W pierwszym etapie $M^{\prime }$ musi dokonać kompresji, czyli odczytać $c$ symboli i zapisać 1 symbol skompresowany. Do tego celu wystarczy jej istnienie około $|{\mathrm{\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^{\prime }$:

{ZO-3-2-rys}{Obszar trzech}

Zapamiętujemy odczyt dzięki stosownemu powiększeniu liczby stanów $M^{\prime }$, które wykonujemy podobnie jak przy kompresji. Tym razem nowy zbiór stanów powiększamy o około ${\mathrm{\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^{\prime }$. W przeciwnym wypadku "obszar trzech" jest modyfikowany kolejnymi 4 ruchami $M^{\prime }$ i cykl rozpoczyna się od nowa. Wiemy jednak, że aby $M$ opuściła obszar trzech komórek $M^{\prime }$ to musi wykonać przynajmniej $c$ ruchów. Przyspieszyliśmy zatem działanie przynajmniej o czynnik $c/8$.

Podsumowując koszt czasowy to $f^{\prime }(n)=n+\lceil n/c\rceil +\lceil 8f(n)/c\rceil <(1+ϵ)n+ϵf(n)$, jeśli $c=\lceil 8/ϵ\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:

(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^{\prime }$ o złożoności pamięciowej $f^{\prime }(n)=ϵf(n)$, gdzie $ϵ>0$.

Skorzystaj z dowodu twierdzenia o liniowym przyspieszaniu.

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^{\prime }$ pamięta $c$ symboli maszyny $M$, więc koszt pamięciowy to $f^{\prime }(n)=\lceil f(n)/c\rceil <ϵf(n)$, jeśli $c=\lceil 1/ϵ\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 [Uzupelnij]

(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 P = Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(n^k) = \bigcup_{j>0} \textnormal{TIME}(n^j)} , to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wielomianowym,

• Klasa NP = Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(n^k) = \bigcup_{j>0} \textnormal{NTIME}(n^j)} , to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wielomianowym,

• Klasa EXP = TIME($2^{n^k}$), to klasa tych języków, które mogą być akceptowane w deterministycznym czasie wykładniczym,

• Klasa NEXP = NTIME($2^{n^k}$), to klasa tych języków, które mogą być akceptowane w niedeterministycznym czasie wykładniczym.

dla klas pamięciowych:

• Klasa L = SPACE({log}$n$), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,

• Klasa NL = NSPACE({log}$n$), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci logarytmicznej,

• Klasa PSPACE = SPACE($n^k$), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wielomianowej,

• Klasa NPSPACE = NSPACE($n^k$), to klasa tych języków, które mogą być akceptowane w niedeterministycznej pamięci wielomianowej,

• Klasa EXPSPACE = SPACE($2^{n^k}$), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci wykładniczej,

• Klasa NEXPSPACE = NSPACE($2^{n^k}$), 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:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(f(n))\subseteq\textnormal{NTIME}(f(n))} , gdyż z definicji, każda maszyna deterministyczna jest maszyną niedeterministyczną,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{SPACE}(f(n))\subseteq\textnormal{NSPACE}(f(n))} , jak wyżej,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NTIME}(f(n))\subseteq\textnormal{NSPACE}(f(n))} , jak wyżej,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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.

Pokaż, że funkcje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil \textnormal{log}n \rceil} , $n^k$, $2^n$ są konstruowalne pamięciowo.

Zastosuj definicję i skonstruuj stosowne maszyny.

Dowód konstruowalności pamięciowej funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \lceil \textnormal{log}n \rceil} opieramy na implementacji klasycznego licznika binarnego. Długość zapisu liczby binarnej $n$ to właśnie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 [Uzupelnij]

(twierdzenie o luce) Istnieje funkcja rekurencyjna $f(n)$ taka, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(f(n))=\textnormal{TIME}(2^{f(n)})} .

Dowód [Uzupelnij]

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,\dots$ 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,\dots ,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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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⩾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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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ę.

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:

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$?

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

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 $|\mathrm{\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ę.

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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:

Uzasadnij każdą z poniższych relacji:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{L}\subseteq\textnormal{NL}\subseteq\textnormal{P}\subseteq\textnormal{NP}\subseteq\textnormal{PSPACE}}

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{PSPACE}\subseteq\textnormal{NPSPACE}\subseteq\textnormal{EXP}\subseteq\textnormal{NEXP}\subseteq\textnormal{EXPSPACE}\subseteq\textnormal{NEXPSPACE}}

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

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NL}\subseteq\textnormal{P}} , korzystamy z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , w tym wypadku

mamy bowiem Parser nie mógł rozpoznać (błąd składni): {\displaystyle c^{\textnormal{log}n}=n^k} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NPSPACE}\subseteq\textnormal{EXP}} , również korzystamy z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{TIME}(c^{f(n)})} , w tym wypadku

mamy bowiem $c^{n^k}=2^{n^{k^{\prime }}}$.

Przyjrzyjmy się bliżej pierwszej serii relacji z poprzedniego ćwiczenia i zobrazujmy ją na rysunku:

{ZO-3-3-rys}{Relacje pomiędzy podstawowymi klasami} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(c^{f(n)})} . Okazuje się, że zachodzi twierdzenie dużo silniejsze:

Twierdzenie [Uzupelnij]

(twierdzenie Savitcha) Jeśli $f(n)$ jest konstruowalna pamięciowo, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{NSPACE}(f(n))\subseteq\textnormal{SPACE}(f^2(n))} .

Dowód [Uzupelnij]

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(Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{log}^2n} ), gdzie $n$ to rozmiar grafu. W naszym wypadku rozmiar grafu to liczba konfiguracji, czyli $c^{f(n)}$, zatem REACHABILITY wymaga czasu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ę Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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$:

{ZO-3-4-rys}{Wierzchołek pośredni}

Potem wywołujemy rekurencyjnie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{PATH}(x,t,i/2)} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ą Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{log}n} pamięci. Razem potrzebujemy Parser nie mógł rozpoznać (błąd składni): {\displaystyle O(\textnormal{log}^2n)} 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!