En la teoría de la complejidad computacional , PSPACE es el conjunto de todos los problemas de decisión que pueden resolverse mediante una máquina de Turing utilizando una cantidad polinomial de espacio .
Si denotamos por SPACE( f ( n )), el conjunto de todos los problemas que pueden ser resueltos por máquinas de Turing usando el espacio O ( f ( n )) para alguna función f 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 ninguna potencia extra. 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. [ cita requerida ]
Se conocen las siguientes relaciones entre PSPACE y las clases de complejidad NL , P , NP , PH , EXPTIME y EXPSPACE (tenga en cuenta que ⊊ denota contención estricta, que no debe confundirse con ⊈):
De la tercera línea se deduce que tanto en la primera como en la segunda, al menos una de las contenciones del conjunto debe ser estricta, pero no se sabe cuál. Se sospecha ampliamente que todas lo son.
Se sabe que las contenciones en la tercera línea son estrictas. La primera se desprende de la diagonalización directa (el teorema de jerarquía espacial , NL ⊊ NPSPACE) y del hecho de que PSPACE = NPSPACE mediante el teorema de Savitch . La segunda se desprende simplemente del teorema de jerarquía espacial.
Los problemas más difíciles en PSPACE son los problemas PSPACE-completos. Consulte PSPACE-completos para ver ejemplos de problemas que se sospecha que están en PSPACE pero no en NP.
La clase PSPACE está cerrada bajo las operaciones unión , complementación y estrella de Kleene .
Una caracterización alternativa de PSPACE es el conjunto de problemas decidibles por una máquina de Turing alterna en tiempo polinomial, a veces llamada APTIME o simplemente AP. [4]
Una caracterización lógica de PSPACE desde la teoría de la complejidad descriptiva es que es el conjunto de problemas expresables en lógica de segundo orden con la adición de un operador de clausura transitiva . No se necesita una clausura transitiva completa; basta con una clausura transitiva conmutativa e incluso formas más débiles. Es la adición de este operador lo que (posiblemente) distingue a PSPACE de PH .
Un resultado importante de la teoría de la complejidad es que PSPACE puede ser caracterizado como todos los lenguajes reconocibles por un sistema de prueba interactivo particular , el que define la clase IP . En este sistema, hay un probador todopoderoso que intenta convencer a un verificador aleatorio en tiempo polinomial de que una cadena está en el lenguaje. Debería poder convencer al verificador con alta probabilidad si la cadena está en el lenguaje, pero no debería poder convencerlo excepto con baja probabilidad si la cadena no está en el lenguaje.
PSPACE se puede caracterizar como la clase de complejidad cuántica QIP . [5]
PSPACE también es igual a P CTC , problemas solucionables por computadoras clásicas que utilizan curvas temporales cerradas , [6] así como a BQP CTC , problemas solucionables por computadoras cuánticas que utilizan curvas temporales cerradas. [7]
Un lenguaje B es PSPACE-completo si está en PSPACE y es PSPACE-duro, lo que significa que para todo A ∈ PSPACE, , donde significa que hay una reducción de muchos a uno en tiempo polinomial de A a B . Los problemas PSPACE-completos son de gran importancia para estudiar los problemas PSPACE porque representan los problemas más difíciles en PSPACE. Encontrar una solución simple para un problema PSPACE-completo significaría que tenemos una solución simple para todos los demás problemas en PSPACE porque todos los problemas PSPACE podrían reducirse a un problema PSPACE-completo. [8]
Un ejemplo de un problema PSPACE-completo es el problema de la fórmula booleana cuantificada (generalmente abreviado como QBF o TQBF ; la T significa "verdadero"). [8]
