En la teoría de la complejidad computacional , un problema de decisión es PSPACE-completo si se puede resolver usando una cantidad de memoria que es polinómica en la longitud de entrada ( espacio polinómico ) y si todos los demás problemas que se pueden resolver en el espacio polinómico se pueden transformar en él. en tiempo polinomial . Los problemas que son completos en PSPACE pueden considerarse como los problemas más difíciles en PSPACE , la clase de problemas de decisión que se pueden resolver en el espacio polinomial, porque una solución a cualquiera de esos problemas podría usarse fácilmente para resolver cualquier otro problema en PSPACE.
Los problemas que se sabe que son completos en PSPACE incluyen la determinación de propiedades de expresiones regulares y gramáticas sensibles al contexto , la determinación de la verdad de fórmulas booleanas cuantificadas , cambios paso a paso entre soluciones de problemas de optimización combinatoria y muchos acertijos y juegos.
Se define que un problema es PSPACE completo si se puede resolver usando una cantidad polinómica de memoria (pertenece a PSPACE) y cada problema en PSPACE se puede transformar en tiempo polinómico en una instancia equivalente del problema dado. [1]
Se sospecha ampliamente que los problemas PSPACE-completos están fuera de las clases de complejidad más famosas P (tiempo polinómico) y NP (tiempo polinómico no determinista), pero eso no se sabe. [2] Se sabe que se encuentran fuera de la clase NC , una clase de problemas con algoritmos paralelos altamente eficientes , porque los problemas en NC se pueden resolver en una cantidad de polinomio espacial en el logaritmo del tamaño de entrada, y la clase de Los problemas que se pueden resolver en una cantidad de espacio tan pequeña están estrictamente contenidos en PSPACE mediante el teorema de la jerarquía espacial .
Las transformaciones que generalmente se consideran al definir la completitud de PSPACE son reducciones muchos-uno en tiempo polinomial , transformaciones que toman una instancia única de un problema de un tipo en una instancia única equivalente de un problema de un tipo diferente. Sin embargo, también es posible definir la completitud utilizando reducciones de Turing , en las que un problema se puede resolver con un número polinómico de llamadas a una subrutina para el otro problema. No se sabe si estos dos tipos de reducciones conducen a diferentes clases de problemas de PSPACE completo. [3] También se han considerado otros tipos de reducciones, como las reducciones de muchos uno que siempre aumentan la longitud de la entrada transformada. [4]
Una versión de la conjetura de Berman-Hartmanis para conjuntos completos de PSPACE establece que todos esos conjuntos se parecen, en el sentido de que todos pueden transformarse entre sí mediante biyecciones de tiempo polinomial . [5]
Dada una expresión regular , determinar si genera cada cadena sobre su alfabeto es PSPACE completo. [6]
El primer problema completo de PSPACE conocido fue el problema verbal para gramáticas deterministas sensibles al contexto . En el problema verbal de gramáticas sensibles al contexto, a uno se le da un conjunto de transformaciones gramaticales que pueden aumentar, pero no pueden disminuir, la longitud de una oración, y desea determinar si estas transformaciones podrían producir una oración determinada. La condición técnica del "determinismo" (lo que implica aproximadamente que cada transformación hace obvio que fue utilizada) asegura que este proceso puede resolverse en el espacio polinomial, y Kuroda (1964) demostró que todo programa (posiblemente no determinista) computable en espacio polinómico el espacio podría convertirse en el análisis de una gramática sensible al contexto, de una manera que preserve el determinismo. [7] En 1970, el teorema de Savitch demostró que PSPACE está cerrado bajo no determinismo, lo que implica que incluso las gramáticas sensibles al contexto no deterministas están en PSPACE. [1]
Un problema estándar de PSPACE completo, utilizado en muchos otros resultados de completitud de PSPACE, es el problema de fórmula booleana cuantificada , una generalización del problema de satisfacibilidad booleana . El problema de la fórmula booleana cuantificada toma como entrada una expresión booleana, con todas sus variables cuantificadas de forma universal o existencial, por ejemplo:
Los problemas de reconfiguración se refieren a la conectividad de un espacio de estados de soluciones a un problema combinatorio. Por ejemplo, probar si dos colores de 4 colores de un gráfico se pueden conectar entre sí mediante movimientos que cambian el color de un vértice a la vez, manteniendo en cada paso un color de 4 colores válido, es PSPACE completo, [8] incluso aunque el mismo problema para 3 colores se puede resolver en tiempo polinomial. [9] Otra familia de problemas de reconfiguración, utilizada de manera similar a las fórmulas booleanas cuantificadas como base para las pruebas de completitud de PSPACE de muchos otros problemas en esta área, involucran una lógica de restricciones no determinista , en la que los estados son orientaciones de un gráfico de restricciones sujeto a ciertas restricciones. sobre cuántas aristas deben orientarse hacia adentro en cada vértice, y en qué los movimientos de un estado a otro invierten la orientación de una sola arista. [10]
El problema de la fórmula booleana cuantificada puede interpretarse como un juego entre dos jugadores, un verificador y un falsificador. Los jugadores realizan movimientos que completan los valores de las variables cuantificadas, en el orden en que están anidadas, con el verificador completando variables existencialmente cuantificadas y el falsificador completando variables universalmente cuantificadas; el juego lo gana el verificador si la fórmula completada se vuelve verdadera, y el falsificador en caso contrario. Una fórmula cuantificada es verdadera si y sólo si el verificador tiene una estrategia ganadora. De manera similar, el problema de determinar el ganador o el perdedor de muchos otros juegos combinatorios resulta ser PSPACE-completo. Ejemplos de juegos que son PSPACE-completo (cuando se generalizan para que puedan jugarse en un tablero) son los juegos Hex y Reversi . Algunos otros juegos generalizados, como el ajedrez , las damas (damas) y el Go , son EXPTIME-completos porque una partida entre dos jugadores perfectos puede ser muy larga, por lo que es poco probable que estén en PSPACE. Pero se convertirán en PSPACE completo si se aplica un límite polinómico en el número de movimientos. [11]
También es posible que los rompecabezas jugados por un solo jugador estén completos en PSPACE. Estos a menudo pueden interpretarse como problemas de reconfiguración [10] e incluyen los juegos de solitario Rush Hour , Mahjong , Atomix y Sokoban , y la computadora mecánica Turing Tumble . [11]
La integridad de PSPACE se basa en la complejidad en función del tamaño de entrada , en el límite a medida que crece sin límite. Los rompecabezas o juegos con un número limitado de posiciones, como el ajedrez en un tablero convencional, no pueden ser completos en PSPACE, porque podrían resolverse en tiempo y espacio constantes utilizando una tabla de búsqueda muy grande . Para formular versiones completas de PSPACE de estos juegos, se deben modificar de manera que su número de posiciones sea ilimitado, por ejemplo, jugándolos en un tablero. En algunos casos, como en el ajedrez, estas extensiones son artificiales.
