PSPACE

W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocą maszyny Turinga wykorzystującej wielomianową przestrzeń.

Formalna definicja

Jeśli oznaczymy przez ${\mathsf {SPACE}}(t(n))$ zestaw wszystkich problemów, które można rozwiązać za pomocą maszyn Turinga wykorzystujących przestrzeń $O(t(n))$ dla pewnej funkcji $t$ o wielkości wejściowej $n,$ wówczas możemy formalnie zdefiniować PSPACE jako

${\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).$

PSPACE jest ścisłym nadzbiorem zbioru języków kontekstowych.

Okazuje się, że pozwalając maszynie Turinga być niedeterministyczną, nie dodaje jej żadnej dodatkowej mocy. Ze względu na twierdzenie Savitcha NPSPACE jest równoważne PSPACE, zasadniczo dlatego, że deterministyczna maszyna Turinga może symulować niedeterministyczną maszynę Turinga, nie wymagając dużo więcej miejsca (chociaż może zużywać znacznie więcej czasu). Uzupełnieniem wszystkich problemów w PSPACE jest także PSPACE, co oznacza, że co-PSPACE = PSPACE.

Relacja między innymi klasami

Reprezentacja relacji między klasami złożoności

Znane są następujące relacje między PSPACE a klasami złożoności NL, P, NP, PH, EXPTIME i EXPSPACE (należy zwrócić uwagę, że $\subsetneq ,$ co oznacza ścisłe zawieranie, to nie to samo co $\nsubseteq$):

${\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}$

Wiadomo, że w pierwszym i drugim wierszu co najmniej jedno z zawierań musi być ścisłe, ale nie wiadomo, które. Powszechnie podejrzewa się, że wszystkie są ścisłe.

PSPACE-zupełność

Język $B$ jest PSPACE-zupełny, jeśli jest w PSPACE i jest trudny dla PSPACE, co oznacza dla wszystkich $A\in {\mathsf {PSPACE}},$ $A\leqslant _{p}B,$ gdzie $A\leqslant _{p}B$ oznacza, że istnieje redukcja z $A$ do $B$ w czasie wielomianowym. Problemy PSPACE-zupełne mają ogromne znaczenie przy badaniu problemów z PSPACE, ponieważ stanowią najtrudniejsze problemy z PSPACE. Znalezienie prostego rozwiązania problemu PSPACE-zupełnego oznaczałoby, że mamy proste rozwiązanie wszystkich innych problemów w PSPACE, ponieważ wszystkie problemy PSPACE można zredukować do problemu PSPACE-zupełnego.

Przykładem problemu pełnego PSPACE-zupełnego jest problem skwantyfikowanej boolowskiej formuły (zwykle w skrócie QBF lub TQBF ; T oznacza „prawda”).