En la teoría de la complejidad computacional , un problema de decisión es PSPACE-completo si se puede resolver utilizando 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 polinómico . Los problemas que son PSPACE-completos pueden considerarse como los problemas más difíciles en PSPACE , la clase de problemas de decisión resolubles en el espacio polinómico, 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 PSPACE-completos 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 rompecabezas y juegos.
Un problema se define como PSPACE-completo si se puede resolver utilizando 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 polinomial) y NP (tiempo polinomial 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 espacio polinomial en el logaritmo del tamaño de entrada, y la clase de problemas resolubles en una cantidad de espacio tan pequeña está estrictamente contenida en PSPACE por el teorema de jerarquía espacial .
Las transformaciones que se suelen considerar para definir la completitud de PSPACE son las reducciones de muchos-uno en tiempo polinomial , transformaciones que toman una única instancia de un problema de un tipo en una única instancia 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 en un número polinomial de llamadas a una subrutina para el otro problema. No se sabe si estos dos tipos de reducciones conducen a diferentes clases de problemas PSPACE-completos. [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 PSPACE-completos establece que todos esos conjuntos son similares, en el sentido de que todos ellos pueden transformarse entre sí mediante biyecciones en tiempo polinomial . [5]
Dada una expresión regular , determinar si genera cada cadena sobre su alfabeto es PSPACE-completo. [6]
El primer problema PSPACE-completo conocido fue el problema verbal para gramáticas deterministas sensibles al contexto . En el problema verbal para gramáticas sensibles al contexto, se da un conjunto de transformaciones gramaticales que pueden aumentar, pero no disminuir, la longitud de una oración, y se desea determinar si una oración dada podría ser producida por estas transformaciones. La condición técnica de "determinismo" (que implica aproximadamente que cada transformación hace obvio que se utilizó) asegura que este proceso puede resolverse en el espacio polinomial, y Kuroda (1964) demostró que cada programa (posiblemente no determinista) computable en el espacio lineal podría convertirse en el análisis sintáctico de una gramática sensible al contexto, de una manera que preserva el determinismo. [7] En 1970, el teorema de Savitch mostró que PSPACE está cerrado bajo el 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 fórmula booleana cuantificada toma como entrada una expresión booleana, con todas sus variables cuantificadas de forma universal o existencial, por ejemplo: La salida del problema es el valor de la expresión cuantificada. Encontrar este valor es PSPACE-completo. [1]
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 4-coloraciones de un grafo pueden conectarse entre sí mediante movimientos que cambian el color de un vértice a la vez, manteniendo en cada paso una 4-coloración válida, es PSPACE-completo, [8] aunque el mismo problema para 3-coloraciones puede resolverse en tiempo polinomial. [9] Otra familia de problemas de reconfiguración, utilizados de manera similar a las fórmulas booleanas cuantificadas como base para las pruebas de completitud PSPACE de muchos otros problemas en esta área, involucran lógica de restricciones no determinista , en la que los estados son orientaciones de un grafo de restricciones sujeto a ciertas restricciones sobre cuántas aristas deben estar orientadas hacia adentro en cada vértice, y en la que los movimientos de estado a estado 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 las variables cuantificadas existencialmente y el falsificador completando las variables cuantificadas universalmente; 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 solo si el verificador tiene una estrategia ganadora. De manera similar, el problema de determinar el ganador o perdedor de muchos otros juegos combinatorios resulta ser PSPACE-completo. Ejemplos de juegos que son PSPACE-completos (cuando se generalizan para que se puedan jugar en un tablero) son los juegos Hex y Reversi . Algunos otros juegos generalizados, como ajedrez , damas (damas) y Go son EXPTIME-completos porque un juego entre dos jugadores perfectos puede ser muy largo, por lo que es poco probable que sean PSPACE. Pero se volverán PSPACE-completos si se impone un límite polinomial en el número de movimientos. [11]
También es posible que los rompecabezas que juega un solo jugador sean PSPACE-completos. Estos a menudo se pueden interpretar como problemas de reconfiguración, [10] e incluyen los juegos de solitario Rush Hour , Mahjong , Atomix y Sokoban , y el ordenador mecánico Turing Tumble . [11]
La completitud de PSPACE se basa en la complejidad como 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 PSPACE-completos, porque podrían resolverse en tiempo y espacio constantes utilizando una tabla de búsqueda muy grande . Para formular versiones PSPACE-completas de estos juegos, deben modificarse de una manera que haga que su número de posiciones sea ilimitado, como por ejemplo jugándolos en un tablero. En algunos casos, como en el ajedrez, estas extensiones son artificiales.
