Tekst źródłowy strony PSPACE

W teorii złożoności obliczeniowej '''PSPACE''' jest zbiorem wszystkich [[Problem decyzyjny (teoria obliczeń)|problemów decyzyjnych]], które można rozwiązać za [[Maszyna Turinga|pomocą maszyny Turinga]] wykorzystującej [[wielomian]]ową przestrzeń.

== Formalna definicja ==
Jeśli oznaczymy przez <math>\mathsf{SPACE}(t(n))</math> zestaw wszystkich problemów, które można rozwiązać za [[Maszyna Turinga|pomocą maszyn Turinga]] wykorzystujących przestrzeń <math>O(t(n))</math> dla pewnej funkcji <math>t</math> o wielkości wejściowej <math>n,</math> wówczas możemy formalnie zdefiniować PSPACE jako<ref name="AB81">Arora & Barak (2009) p. 81.</ref>
: <math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k).</math>

PSPACE jest ścisłym nadzbiorem zbioru języków [[Język kontekstowy|kontekstowych]].

Okazuje się, że pozwalając maszynie Turinga być niedeterministyczną, nie dodaje jej żadnej dodatkowej mocy. Ze względu na twierdzenie Savitcha<ref name="AB85">Arora & Barak (2009) p. 85.</ref> NPSPACE jest równoważne PSPACE, zasadniczo dlatego, że deterministyczna maszyna Turinga może symulować [[Niedeterministyczna maszyna Turinga|niedeterministyczną maszynę Turinga]], nie wymagając dużo więcej miejsca (chociaż może zużywać znacznie więcej czasu)<ref name="AB86">Arora & Barak (2009) p. 86.</ref>. [[Dopełnienie (teoria złożoności)|Uzupełnieniem]] wszystkich problemów w PSPACE jest także PSPACE, co oznacza, że co-PSPACE {{=}} PSPACE.

== Relacja między innymi klasami ==
[[Plik:Complexity subsets pspace.svg|mały|prawo|300x300px|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, [[Problem P|P]], [[Problem NP|NP]], PH, [[EXPTIME]] i EXPSPACE (należy zwrócić uwagę, że <math>\subsetneq,</math> co oznacza ścisłe zawieranie, to nie to samo co <math>\nsubseteq</math>):
: <math>\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}</math>

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 <math>B</math> jest ''PSPACE-zupełny,'' jeśli jest w PSPACE i jest ''trudny'' dla PSPACE, co oznacza dla wszystkich <math>A \in \mathsf{PSPACE},</math> <math>A \leqslant_p B,</math> gdzie <math>A \leqslant_p B</math> oznacza, że istnieje redukcja z <math>A</math> do <math>B</math> 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<ref name="AB83">Arora & Barak (2009) p. 83.</ref>.

Przykładem problemu pełnego PSPACE-zupełnego jest problem skwantyfikowanej boolowskiej formuły (zwykle w skrócie '''QBF''' lub '''TQBF''' ; '''T''' oznacza „prawda”)<ref name="AB83" />.

== Przypisy ==
{{Przypisy}}

{{klasy złożoności}}

[[Kategoria:Klasy złożoności]]