Clase PSPACE

La clase de complejidad PSPACE es el conjunto de todos los problemas de resolución en la teoría de la complejidad computacional que puede resolver una máquina de Turing con una restricción de espacio polinomial .

Máquina de Turing con restricción de espacio polinomial

Si es cierto que para una máquina de Turing dada existe un polinomio p ( n ) tal que, en cualquier entrada de tamaño n , visitará como máximo p ( n ) celdas, entonces tal máquina se llama máquina de Turing con un restricción de espacio polinomial .

Se puede demostrar que:

1. Si una máquina de Turing con espacio polinomialmente acotado por p ( n ) , entonces existe una constante c para la cual esta máquina admite su entrada de longitud n en no más que pasos. $c^{1+p(n)}$

De ello se deduce que todos los lenguajes de máquina de Turing con restricciones de espacio polinomial son recursivos .

Clases PSPACE, NPSPACE

La clase de lenguaje PSPACE es el conjunto de lenguajes permitidos por una máquina de Turing determinista con una restricción de espacio polinomial.

La clase de lenguaje NPSPACE es el conjunto de lenguajes permitidos por una máquina de Turing no determinista con una restricción de espacio polinomial.

Las siguientes afirmaciones son verdaderas para las clases de lenguaje PSPACE y NPSPACE:

1. PESPACIO = NPESPACIO (este hecho se demuestra por el teorema de Savitch )

2. Los lenguajes sensibles al contexto son un subconjunto de PSPACE

3. ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$

cuatro ${\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}$

5. Si el lenguaje pertenece a PSPACE, entonces hay una máquina de Turing con una restricción de espacio polinomial tal que se detiene en pasos para algún c y un polinomio p ( n ) . $c^{p(n)}$

Se sabe que al menos uno de los tres símbolos de inclusión en el enunciado debe ser estricto (es decir, excluir la igualdad de los conjuntos, la relación entre los que describe), pero no se sabe cuál de ellos. Además, al menos un subconjunto en una declaración debe ser propio (es decir, al menos un carácter de inclusión debe ser estricto). Se supone que todas estas inclusiones son estrictas . $\subseteq$ ${\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}$ ${\ estilo de visualización (\ subconjunto)}$ ${\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}$ ${\ estilo de visualización (\ subconjunto)}$

Desafío PSPACE-Complete

Un problema PSPACE-completo es un problemasegún Karpse puedentiempo polinomial. ${\mbox{L}}\in {\mbox{PSPACE)),$

Se conocen los siguientes hechos sobre el problema PSPACE-completo:

Si es un problema completo de PSPACE, entonces ${\mbox{L}}$

una. ${\mbox{L}}\in {\mbox{P}}\Rightarrow {\mbox{P}}={\mbox{PSPACE}};$

2. ${\mbox{L}}\in {\mbox{NP}}\Rightarrow {\mbox{NP}}={\mbox{PSPACE}}.$

Un ejemplo de un problema completo de PSPACE: encontrar fórmulas booleanas verdaderas con cuantificadores .

Literatura

John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M. : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .

Hopcroft, Motwani, Ullman: "Introducción a la teoría, lenguajes y computación de autómatas"

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS