PSPACE

En teoria de la complexitat, la classe de complexitat PSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing usant un espai polinòmic.

Definició formal

Si anotem amb SPACE(t(n)) el conjunt de tots els problemes que es poden resoldre amb una màquina de Turing usant O(t(n)) d'espai per alguna funció t de la mida de l'entrada n, llavors es pot definir PSPACE com

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

PSPACE és un superconjunt estricte del conjunt de llenguatges sensibles al context.

Resulta que fent que la màquina de Turing sigui no determinista no afegeix cap potència extra. Donat el teorema de Savitch, NPSPACE és equivalent a NSPACE, bàsicament perquè una màquina de Turing determinista pot simular una de no determinista sense que li calgui més espai, tot i que pot tardar molt més temps. També, el complementari de tots els problemes de PSPACE estan a PSPACE, fent que PSPACE-complementari = PSPACE.

Relació amb d'altres classes

Una representació de la relació entre classes de complexitat

Les següents relacions son conegudes entre PSPACE i les classes de complexitat NL, P, NP, PH, EXPTIME i EXPSPACE (⊊ vol dir conté estricte, i no és el mateix que ⊈):

${\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}}$

De les dues primeres línies se sap que almenys un dels conjunts conté estrictament un altre, però no se sap quin. Se suposa que tots ho son.