PSPACE-completo

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 polinomial) y si cualquier otro problema que pueda resolverse en espacio polinomial se puede transformar en tiempo polinomial. Los problemas que son PSPACE-completo pueden considerarse como los problemas más difíciles de PSPACE, la clase de problemas de decisión que se pueden resolver en el espacio polinomial, porque una solución a cualquiera de estos 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 las propiedades de las expresiones regulares y las gramáticas sensibles al contexto, la determinación de la verdad de las fórmulas booleanas cuantificadas, los cambios paso a paso entre las soluciones de los problemas de optimización combinatoria y muchos rompecabezas y juegos.

Teoría

Un problema se define como PSPACE-completo si se puede resolver utilizando una cantidad polinomial de memoria (pertenece a PSPACE) y cada problema en PSPACE se puede transformar en tiempo polinomial en una instancia equivalente del problema dado.

Se sospecha ampliamente que los problemas de PSPACE-completo 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. 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 problemas que se pueden resolver en una cantidad tan pequeña de espacio está estrictamente contenida en PSPACE por el teorema de la jerarquía espacial.

Las transformaciones que generalmente se consideran para definir la completitud de PSPACE son reducciones polinomiales de tiempo muchos-uno, 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 usando reducciones de Turing, en las que un problema puede resolverse 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. También se han considerado otros tipos de reducciones, como las reducciones muchos-uno que siempre aumentan la longitud de la entrada transformada.

Una versión de la conjetura de Berman-Hartmanis para conjuntos completos de PSPACE establece que todos estos conjuntos se parecen, en el sentido de que todos pueden transformarse entre sí mediante biyecciones de tiempo polinomial.

Ejemplos

Lenguajes formales

Dada una expresión regular ${displaystyle R.$, determinar si genera cada cadena sobre su alfabeto es PSPACE-completo.

El primer problema completo de PSPACE conocido fue el problema de palabras para gramáticas deterministas sensibles al contexto. En el problema verbal para gramáticas sensibles al contexto, se le da a uno un conjunto de transformaciones gramaticales que pueden aumentar, pero no disminuir, la longitud de una oración, y desea determinar si estas transformaciones podrían producir una oración dada. La condición técnica del "determinismo" (lo que implica aproximadamente que cada transformación hace que sea obvio que se usó) asegura que este proceso se puede resolver en el espacio polinomial, y Kuroda (1964) mostró 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. 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.

Lógica

Un problema estándar de PSPACE-completo, utilizado en muchos otros resultados de PSPACE-completo, 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:

$${displaystyle exists x_{1},forall x_{2},exists x_{3},forall x_{4}:(x_{1}lor neg x_{3}lor x_{4})land (neg x_{2}lor x_{3}neg x_{4}). }$$

Reconfiguración

Los problemas de reconfiguración se refieren a la conectividad de un espacio de estado de soluciones a un problema combinatorio. Por ejemplo, probar si dos colores de 4 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 válido, es PSPACE-completo, aunque el mismo El problema de 3 coloraciones se puede resolver en tiempo polinomial. 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, implica una lógica de restricción no determinista, en la que los estados son orientaciones de un gráfico de restricción sujeto a ciertas restricciones sobre cuántos los bordes deben estar orientados hacia adentro en cada vértice, y en los que los movimientos de un estado a otro invierten la orientación de un solo borde.

Rompecabezas y juegos

El problema de fórmula booleana cuantificada puede ser interpretado como un juego por dos jugadores, un verificador y un falsificador. Los jugadores hacen movimientos que llenan valores para las variables cuantificadas, en el orden que se anidan, con el relleno verificador en variables existencialmente cuantificadas y el relleno falsificador en variables universalmente cuantificadas; el juego es ganado por el verificador si la fórmula llenada se hace realidad, y por el falsificador de otra manera. Una fórmula cuantificada es verdadera si y sólo si el verificador tiene una estrategia ganadora. Del mismo modo, el problema de determinar el ganador o perdedor de muchos otros juegos combinatorios resulta ser PSPACE-completo. Ejemplos de juegos que son PSPACE-completo (cuando se generalizan para que puedan jugar en un ${displaystyle ntimes n}$ bordo) son los juegos Hex y Reversi. Algunos otros juegos generalizados, como ajedrez, damas (traídos), y Go son completos EXPTIME porque un juego entre dos jugadores perfectos puede ser muy largo, por lo que es poco probable que estén en PSPACE. Pero se convertirán en PSPACE-completo si se aplica un polinomio ligado al número de movimientos.

También es posible que los rompecabezas jugados por un solo jugador sean completos para PSPACE. Estos a menudo pueden interpretarse como problemas de reconfiguración e incluyen los juegos de solitario Rush Hour, Mahjong, Atomix y Sokoban, y la computadora mecánica Turing Tumble.

PSPACE-completeness se basa en la complejidad como función del tamaño de entrada ${displaystyle n}$, en el límite como ${displaystyle n}$ crece sin límites. Puzzles o juegos con un número ilimitado de posiciones como el ajedrez en un convencional ${displaystyle 8times 8}$ El tablero no puede ser completo de PSPACE, porque podrían ser resueltos en tiempo y espacio constantes utilizando una mesa de búsqueda muy grande. Para formular versiones completas de PSPACE de estos juegos, deben ser modificadas de una manera que hace que su número de posiciones no abunde, como por ejemplo jugando en un ${displaystyle ntimes n}$ A bordo en su lugar. En algunos casos, como para el ajedrez, estas extensiones son artificiales.