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

[section]

{Lemma}

{Twierdzenie}

{Definicja}

{Przykład}

{Ćwiczenie}

{Observation}

{\hfill $◻$ }

{}

\fancyhf{} \lhead{\leftmark} \rhead{\thepage}

\addtolength{\textheight}{0.5cm} \addtolength{\textwidth}{0.8cm} \addtolength{\oddsidemargin}{ -0.4cm} \addtolength{\evensidemargin}{ -0.4cm} \setlength{\unitlength}{1mm} \headheight 14.6pt

{\Huge \bfInformacje}

\begin_center

\begin_tabular{|l|l|} \hline Przedmiot & Złożoność obliczeniowa
\hline Moduł & 3
\hline Tytuł & Klasy złożoności obliczeniowej
\hline Opracowanie & Przemysław Broniek
\hline \end_tabular

\end_center

{\Huge \bfSyllabus}

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.

\newpage

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

Dowód [Uzupelnij]

{{{3}}}

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:

Szablon:Theorem

Szablon:\noindent ''Wskazówka: ''

Szablon:\noindent ''Rozwiązanie: ''

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(\textnormal{log} $n$ ), to klasa tych języków, które mogą być akceptowane w deterministycznej pamięci logarytmicznej,

Klasa NL = NSPACE(\textnormal{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.

Szablon:Theorem

Szablon:\noindent ''Wskazówka: ''

Szablon:\noindent ''Rozwiązanie: ''

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:

Szablon:Theorem

Szablon:\noindent ''Wskazówka: ''

Szablon:\noindent ''Rozwiązanie: ''

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:

Szablon:Theorem

Szablon:\noindent ''Wskazówka: ''

Szablon:\noindent ''Rozwiązanie: ''

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

\vspace{1cm} \begin_center \includegraphics[width=10cm]{ZO-3-3-rys.jpg}
Relacje pomiędzy podstawowymi klasami \end_center \vspace{1cm}

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]

{{{3}}}

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^{*} ∖ 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 $ϕ$ 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 ϕ$ jest formułą zawsze spełnioną, czyli jest tautologią logiczną.

COMPLEMENT nie jest ściśle dopełnieniem języka, gdyż $\overline{S A T}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 [Uzupelnij]

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

Dowód [Uzupelnij]

{{{3}}}

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

(twierdzenie o hierarchii czasowej) Jeśli $f (n)$ jest konstruowalna czasowo oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(n) \in o(f(n)/\textnormal{log}f(n))} to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{SPACE}(n^{\epsilon_1})\subsetneq\textnormal{SPACE}(n^{\epsilon_2})} , gdy $0 ⩽ ϵ_{1} < ϵ_{2}$ ,

z własności funkcji wielomianowej,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{TIME}(n^{\epsilon_1})\subsetneq\textnormal{TIME}(n^{\epsilon_2})} , gdy $1 ⩽ ϵ_{1} < ϵ_{2}$ , jak wyżej,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{L}\subsetneq\textnormal{PSPACE}} , gdyż logarytm rośnie wolniej niż funkcja wielomianowa,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{P}\subsetneq\textnormal{EXP}} , korzystamy z własności, że każdy wielomian rośnie wolniej

niż funkcja subwykładnicza Parser nie mógł rozpoznać (błąd składni): {\displaystyle n^{\textnormal{log}n}} a ta z kolei rośnie wolniej, niż każda funkcja wykładnicza.

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