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 ${\displaystyle {\mathsf {SPACE}}(t(n))}$ zestaw wszystkich problemów, które można rozwiązać za pomocą maszyn Turinga wykorzystujących przestrzeń ${\displaystyle O(t(n))}$ dla pewnej funkcji ${\displaystyle t}$ o wielkości wejściowej ${\displaystyle n,}$ wówczas możemy formalnie zdefiniować PSPACE jako^[1]

${\displaystyle {\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^[2] 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)^[3]. 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 ${\displaystyle \subsetneq ,}$ co oznacza ścisłe zawieranie, to nie to samo co ${\displaystyle \nsubseteq }$):

${\displaystyle {\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 ${\displaystyle B}$ jest PSPACE-zupełny, jeśli jest w PSPACE i jest trudny dla PSPACE, co oznacza dla wszystkich ${\displaystyle A\in {\mathsf {PSPACE}},}$ ${\displaystyle A\leqslant _{p}B,}$ gdzie ${\displaystyle A\leqslant _{p}B}$ oznacza, że istnieje redukcja z ${\displaystyle A}$ do ${\displaystyle 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^[4].

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

Przypisy

1. Arora & Barak (2009) p. 81.
2. Arora & Barak (2009) p. 85.
3. Arora & Barak (2009) p. 86.
4. Arora & Barak (2009) p. 83.