PSPACE-completo

Dada una expresión regular${\displaystyle R}$, determinar si genera cada cadena sobre su alfabeto es PSPACE-completo. ^{[ 6 ]} La prueba se realiza tomando una máquina de Turing${\displaystyle M}$y una cantidad de espacio codificada unaria${\displaystyle n}$y construir una expresión regular que acepte una cadena si y solo si no logra codificar una secuencia válida de estados de${\displaystyle M}$que comienza en${\displaystyle M}$configuración inicial y finaliza en${\displaystyle M}$aceptando su aporte, con como máximo${\displaystyle n}$Las celdas de la cinta están siendo visitadas.

El primer problema conocido que cumple con el principio PSPACE fue el problema de la palabra para gramáticas deterministas sensibles al contexto . En este problema, se proporciona un conjunto de transformaciones gramaticales que pueden aumentar, pero no disminuir, la longitud de una oración, y se busca determinar si una oración dada puede generarse mediante estas transformaciones. La condición técnica de "determinismo" (que implica, aproximadamente, que cada transformación deja claro que se ha utilizado) garantiza que este proceso pueda resolverse en espacio polinomial, y Kuroda (1964) demostró que todo programa (posiblemente no determinista) computable en espacio lineal podría convertirse en el análisis sintáctico de una gramática sensible al contexto, de manera que se preserve el determinismo. ^{[ 7 ]} En 1970, el teorema de Savitch demostró que PSPACE es cerrado bajo el no determinismo, lo que implica que incluso las gramáticas sensibles al contexto no deterministas pertenecen a PSPACE. ^{[ 1 ]}

Un problema estándar de PSPACE-completitud, utilizado en muchos otros resultados de PSPACE-completitud, es el problema de la 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}\lor \neg x_{4}).}$$ El resultado 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 coloraciones de cuatro colores 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 coloración de cuatro colores válida, es PSPACE-completo, ^{[ 8 ]} aunque el mismo problema para coloraciones de tres colores puede resolverse en tiempo polinomial. ^{[ 9 ]} Otra familia de problemas de reconfiguración, utilizada de forma similar a las fórmulas booleanas cuantificadas como base para las pruebas de completitud PSPACE de muchos otros problemas en esta área, involucra 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 el perdedor de muchos otros juegos combinatorios resulta ser PSPACE-completo. Ejemplos de juegos que son PSPACE-completos (cuando se generalizan de manera que se puedan jugar en un${\displaystyle n\times n}$Algunos juegos generalizados, como el ajedrez , las damas y el Go , son EXPTIME-completos porque una partida entre dos jugadores perfectos puede ser muy larga, por lo que es improbable que estén en PSPACE. Pero se volverán PSPACE-completos si se impone una cota polinómica al número de movimientos. ^{[ 11 ]}

También es posible que los rompecabezas jugados por un solo jugador sean PSPACE-completos. 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 completitud de PSPACE se basa en la complejidad en función del tamaño de entrada.${\displaystyle n}$, en el límite como${\displaystyle n}$crece sin límites. Rompecabezas o juegos con un número limitado de posiciones, como el ajedrez en un tablero convencional.${\displaystyle 8\times 8}$El tablero no puede ser PSPACE-completo, 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 manera que su número de posiciones sea ilimitado, como por ejemplo jugándolos en un${\displaystyle n\times n}$tablero en su lugar. En algunos casos, como en el ajedrez, estas extensiones son artificiales.