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 $𝖲𝖯𝖠𝖢𝖤(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

$𝖯𝖲𝖯𝖠𝖢𝖤=\bigcup _{k\in \mathbb{N}}𝖲𝖯𝖠𝖢𝖤(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 $⊊,$ co oznacza ścisłe zawieranie, to nie to samo co $⊈$):

$\begin{array}{c}𝖭𝖫\mathsf{\subseteq }𝖯\mathsf{\subseteq }𝖭𝖯\mathsf{\subseteq }𝖯𝖧\mathsf{\subseteq }𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{\subseteq }𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖭𝖫\mathsf{⊊}𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{⊊}𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤\\ 𝖯\mathsf{⊊}𝖤𝖷𝖯𝖳𝖨𝖬𝖤\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 𝖯𝖲𝖯𝖠𝖢𝖤,$ $A{⩽}_{p}B,$ gdzie $A{⩽}_{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”).