PSPACE

Problema sin resolver en informática

⁠${\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}}$⁠

Más problemas sin resolver en informática

En la teoría de la complejidad computacional , PSPACE es el conjunto de todos los problemas de decisión que pueden ser resueltos por una máquina de Turing utilizando una cantidad polinómica de espacio .

Si denotamos por${\displaystyle {\mathsf {ESPACIO}}(f(n))}$el conjunto de todos los problemas que pueden ser resueltos por máquinas de Turing utilizando${\displaystyle O(f(n))}$espacio para alguna función${\displaystyle f}$del tamaño de entrada${\displaystyle n}$, entonces podemos definir${\displaystyle {\mathsf {PSPACE}}}$formalmente como ^{[ 1 ]}

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

Resulta que permitir que la máquina de Turing sea no determinista no agrega ninguna potencia adicional. Debido al teorema de Savitch , ^{[ 2 ]}${\displaystyle {\mathsf {NPSPACE}}}$es equivalente a${\displaystyle {\mathsf {PSPACE}}}$, porque una máquina de Turing determinista puede simular una máquina de Turing no determinista mientras eleva aproximadamente al cuadrado la cantidad de espacio, y elevar al cuadrado convierte polinomios en polinomios (más grandes). ^{[ 3 ]} Además, los complementos de todos los problemas en${\displaystyle {\mathsf {PSPACE}}}$también están en${\displaystyle {\mathsf {PSPACE}}}$, lo que significa que${\displaystyle {\mathsf {coPSPACE}}={\mathsf {PSPACE}}}$. ^{[ 4 ]}

Se conocen las siguientes relaciones entre PSPACE y las clases de complejidad NL , P , NP , PH , EXPTIME y EXPSPACE (usamos aquí${\displaystyle \subset }$para denotar contención estricta, es decir, un subconjunto propio, mientras que${\displaystyle \subseteq }$incluye la posibilidad de que los dos conjuntos sean iguales):

${\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subset PSPACE\subset EXPSPACE}}\\{\mathsf {P\subset EXPTIME}}\end{array}}}$

De la tercera línea se deduce que, tanto en la primera como en la segunda línea, al menos una de las exclusiones del conjunto debe ser estricta, pero se desconoce cuál. Se sospecha que todas son estrictas.

Se sabe que las dos exclusiones de la tercera línea son estrictas. La primera se deduce de la diagonalización directa (el teorema de jerarquía espacial , NL ⊂ NPSPACE) y del hecho de que PSPACE = NPSPACE según el teorema de Savitch . La segunda se deduce 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 pertenecen a PSPACE pero no a 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 alternante en tiempo polinomial, a veces llamado APTIME o simplemente AP. ^{[ 5 ]}

Una caracterización lógica de PSPACE desde la teoría de la complejidad descriptiva es que se trata del conjunto de problemas expresables en lógica de segundo orden con la adición de un operador de cierre transitivo . No se requiere un cierre transitivo completo; basta con un cierre transitivo conmutativo 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 caracterizarse 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 de tiempo polinomial de que una cadena pertenece al lenguaje. Debería poder convencer al verificador con alta probabilidad si la cadena pertenece al lenguaje, pero no debería poder convencerlo salvo con baja probabilidad si la cadena no pertenece al lenguaje.

PSPACE puede caracterizarse como la clase de complejidad cuántica QIP . ^{[ 6 ]}

PSPACE también es igual a P _CTC , problemas resolubles por computadoras clásicas que utilizan curvas temporales cerradas , ^{[ 7 ]} así como a BQP _CTC , problemas resolubles por computadoras cuánticas que utilizan curvas temporales cerradas. ^{[ 8 ]}

Un lenguaje B es PSPACE-completo si está en PSPACE y es PSPACE-difícil, lo que significa que para todo A ∈ PSPACE,${\displaystyle A\leq _{\text{P}}B}$, dónde${\displaystyle A\leq _{\text{P}}B}$Esto significa que existe una reducción de muchos a uno en tiempo polinomial de A a B. Los problemas PSPACE-completos son de gran importancia para el estudio de los problemas PSPACE porque representan los problemas más difíciles en PSPACE. Encontrar una solución simple a un problema PSPACE-completo significaría que tenemos una solución simple a todos los demás problemas en PSPACE porque todos los problemas PSPACE podrían reducirse a un problema PSPACE-completo. ^{[ 9 ]}

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"). ^{[ 9 ]}

• Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4. Zbl 1193.68112 . 

• Papadimitriou, Christos (1993). Complejidad computacional (1.ª  ed.). Addison Wesley. ISBN 0-201-53082-1.Capítulo 19: Espacio polinomial, págs.  455–490.
• Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª  ed.). Thomson Course Technology. ISBN 0-534-95097-3.Capítulo 8: Complejidad espacial
• Williams, Ryan (25-02-2025). "Simulación del tiempo con espacio de raíz cuadrada". arXiv : 2502.17779 [ cs.CC ].

• Complexity Zoo : PSPACE