ESPACIO P

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 de espacio polinomial.

Definición formal

Si denotamos por ESPACIO(f(n)), el conjunto de todos los problemas que pueden ser resueltos por las máquinas de Turing usando O (f(n)) espacio para alguna función f del tamaño de entrada n, entonces podemos definir PSPACE formalmente como

PSPACE=⋃ ⋃ k▪ ▪ NSPACE()nk).{displaystyle {mathsf {fnK}=bigcup _{kin mathbb {N} {mthsf {SPACE}(n^{k}).}

PSPACE es un superconjunto estricto del conjunto de lenguajes sensibles al contexto.

Resulta que permitir que la máquina de Turing sea no determinista no agrega ningún poder extra. Debido al teorema de Savitch, 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). Además, los complementos de todos los problemas en PSPACE también están en PSPACE, lo que significa que co-PSPACE = PSPACE.

Relación entre otras clases

Representación de la relación entre las clases de complejidad

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 ⊈):

NL⊆ ⊆ P⊆ ⊆ NP⊆ ⊆ PH⊆ ⊆ PSPACEPSPACE⊆ ⊆ EXPTIME⊆ ⊆ EXPSPACENL⊊ ⊊ PSPACE⊊ ⊊ EXPSPACEP⊊ ⊊ EXPTIME{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {NLsubseteq Psubseteq NPsubseteq PHsubseteq "PSPACE" EXPTIMEsubseteq EXPSPACE}\{mathsf {NLsubsetneq PSPACEsubsetneq ¿Qué?.

De la tercera línea se deduce que tanto en la primera como en la segunda línea, al menos una de las contenciones establecidas debe ser estricta, pero no se sabe cuál. Se sospecha ampliamente que todos son estrictos.

Se sabe que las medidas de contención de la tercera línea son estrictas. El primero se deriva de la diagonalización directa (el teorema de la jerarquía espacial, NL ⊊ NPSPACE) y el hecho de que PSPACE = NPSPACE a través del teorema de Savitch. El segundo se sigue simplemente del teorema de la jerarquía espacial.

Los problemas más difíciles en PSPACE son los problemas completos de PSPACE. Consulte PSPACE-complete para ver ejemplos de problemas que se sospecha que están en PSPACE pero no en NP.

Propiedades de cierre

La clase PSPACE se cierra bajo unión de operaciones, complementación y estrella Kleene.

Otras caracterizaciones

Una caracterización alternativa de PSPACE es el conjunto de problemas decidibles por una máquina de Turing alterna en tiempo polinomial, a veces llamado APTIME o simplemente AP.

Una caracterización lógica de PSPACE de la teoría descriptiva de la complejidad es que es el conjunto de problemas expresables en lógica de segundo orden con la adición de un operador de cierre transitivo. No se necesita un cierre transitivo completo; una clausura transitiva conmutativa e incluso formas más débiles son suficientes. 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 se puede caracterizar 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 está en el lenguaje. Debería poder convencer al verificador con alta probabilidad si la cadena está en el idioma, pero no debería poder convencerlo excepto con baja probabilidad si la cadena no está en el idioma.

PSPACE se puede caracterizar como el QIP de clase de complejidad cuántica.

PSPACE también es igual a P_CTC, problemas que pueden resolver las computadoras clásicas usando curvas temporales cerradas, así como BQP_CTC, problemas que pueden resolver las computadoras cuánticas usando curvas temporales cerradas curvas.

PSPACE-integridad

Un idioma B es PSPACE-completo si está en PSPACE y es PSPACE-hard, lo que significa para todos A ANTE PSPACE, A≤ ≤ PB{displaystyle Aleq _{text{P}B}, donde A≤ ≤ PB{displaystyle Aleq _{text{P}B} significa que hay una reducción polinomio-tiempo muchos-uno de A a B. Los problemas completos de PSPACE son de gran importancia para estudiar problemas de PSPACE porque representan los problemas más difíciles en PSPACE. Encontrar una solución simple a un problema completo de PSPACE significaría que tenemos una solución sencilla a todos los demás problemas en PSPACE porque todos los problemas de PSPACE podrían reducirse a un problema completo de PSPACE.

Un ejemplo de un problema PSPACE-completo es el problema de la fórmula booleana cuantificada (normalmente abreviado como QBF o TQBF; la T significa 'verdadero').