PSPACE

Problema no resuelto 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 puede resolver una máquina de Turing utilizando una cantidad polinomial de espacio .

Definición formal

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]

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {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 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.

Relación entre otras clases

Una representación de la relación entre 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 ⊈):

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

Se sabe que en la primera y 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.

Se sabe que las 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 deriva simplemente del teorema de la jerarquía espacial.

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

Propiedades de cierre

La clase PSPACE está cerrada bajo operaciones unión , complementación y estrella de Kleene .

Otras caracterizaciones

Una caracterización alternativa de PSPACE es el conjunto de problemas que puede decidir una máquina de Turing alternante en tiempo polinomial, a veces llamado APTIME o simplemente AP. ^[4]

Una caracterización lógica de PSPACE a partir de la teoría de la complejidad descriptiva es que es el conjunto de problemas que se pueden expresar 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 y formas aún más débiles son suficientes. Es la adición de este operador lo que (posiblemente) distingue 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 de tiempo polinomial aleatorio de que hay una cadena en el idioma. 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 la clase de complejidad cuántica QIP . ^[5]

PSPACE también es igual a P _CTC , problemas que se pueden resolver por computadoras clásicas usando curvas cerradas en forma de tiempo , ^[6] así como a BQP _CTC , problemas que se pueden resolver por computadoras cuánticas usando curvas cerradas en forma de tiempo. ^[7]

Completitud de PSPACE

Artículo principal: PSPACE-complete

Una lengua B es PSPACE-completa si está en PSPACE y es PSPACE-dura, lo que significa para todos A ∈ PSPACE, donde los medios que hay un tiempo polinomio mucho-uno la reducción de A a B . Los problemas completos de PSPACE son de gran importancia para estudiar los problemas de PSPACE porque representan los problemas más difíciles en PSPACE. Encontrar una solución simple para un problema de PSPACE completo significaría que tenemos una solución simple para todos los demás problemas en PSPACE porque todos los problemas de PSPACE podrían reducirse a un problema de PSPACE completo. ^[8]${\displaystyle A\leq _{p}B}$${\displaystyle A\leq _{p}B}$

Un ejemplo de un problema completo de PSPACE es el problema de fórmula booleana cuantificada (generalmente abreviado como QBF o TQBF ; la T significa "verdadero"). ^[8]

Referencias

1. Arora y Barak (2009) p.81
2. Arora y Barak (2009) p.85
3. Arora y Barak (2009) p.86
4. Arora y Barak (2009) p.100
5. Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (julio de 2009). "QIP = PSPACE". arXiv : 0907.4737 .
6. S. Aaronson (marzo de 2005). "Problemas NP-completos y realidad física". Noticias SIGACT . arXiv : quant-ph / 0502072 . Código bibliográfico : 2005quant.ph..2072A ..
7. Watrous, John; Aaronson, Scott (2009). "Las curvas cerradas en forma de tiempo hacen equivalentes a la computación cuántica y clásica". Actas de la Royal Society A: Ciencias Matemáticas, Físicas e Ingeniería . 465 (2102): 631. arXiv : 0808.2669 . Código bibliográfico : 2009RSPSA.465..631A . doi : 10.1098 / rspa.2008.0350 .
8. Arora y Barak (2009) p.83

• Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4. Zbl  1193.68112 .
• Sipser, Michael (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 0-534-94728-X. Sección 8.2–8.3 (The Class PSPACE, PSPACE-completeness), págs. 281–294.
• Papadimitriou, Christos (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1. Capítulo 19: Espacio polinómico, págs. 455–490.
• Sipser, Michael (2006). Introducción a la Teoría de la Computación (2ª ed.). Tecnología del curso Thomson. ISBN 0-534-95097-3. Capítulo 8: Complejidad espacial
• Complejidad Zoo : PSPACE