PSPACE
En la teoría de la complejidad computacional , PSPACE es el conjunto de todos los problemas de decisión que puede resolver una máquina de Turing utilizando una cantidad polinomial de espacio .
Si denotamos por ESPACIO ( t ( n )), el conjunto de todos los problemas que pueden ser resueltos por máquinas de Turing usando O ( t ( n )) espacio para alguna función t del tamaño de entrada n , entonces podemos definir PSPACE formalmente como [1]
Resulta que permitir que la máquina de Turing sea no determinista no agrega ningún poder adicional. Debido al teorema de Savitch , [2] NPSPACE es equivalente a PSPACE, esencialmente porque una máquina de Turing determinista puede simular una máquina de Turing no determinista sin necesitar mucho más espacio (aunque puede usar mucho más tiempo). [3] Además, los complementos de todos los problemas en PSPACE también están en PSPACE, lo que significa que co-PSPACE = PSPACE.
Se conocen las siguientes relaciones entre PSPACE y las clases de complejidad NL , P , NP , PH , EXPTIME y EXPSPACE (tenga en cuenta que ⊊, que significa contención estricta, no es lo mismo que ⊈):
De la tercera línea se deduce que tanto en la primera como en la segunda línea, al menos una de las contenciones configuradas debe ser estricta, pero no se sabe cuál. Se sospecha ampliamente que todos son estrictos.
