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 polinomial en la longitud de entrada ( espacio polinomial ) y si todos los demás problemas que se pueden resolver en el espacio polinomial se pueden transformar en él. en tiempo polinomial . Los problemas que están completos en PSPACE pueden considerarse los problemas más difíciles en PSPACE , porque una solución a cualquiera de estos problemas podría usarse fácilmente para resolver cualquier otro problema en PSPACE .
Se sospecha ampliamente que los problemas completos de PSPACE están fuera de las clases de complejidad más famosas P y NP , pero eso se desconoce. [1] 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 contenido en PSPACE por el teorema de la jerarquía espacial .
Ejemplos de
Expresiones regulares y autómatas
Dada una expresión regular R , determinar si genera cada cadena sobre su alfabeto es PSPACE-completo. [2]
Un resultado relacionado es que la clase de lenguajes reconocibles con cero error por autómatas con cinta aleatoria infinita bidireccional es igual al espacio lineal no determinista . Esto es válido tanto para el acceso unidireccional de dos vías como para varios pasos a la entrada. Probar si un autómata (con cinta aleatoria infinita de dos vías) acepta una palabra con error cero es NSPACE (O (kn)) completo, donde n es el tamaño de entrada yk es el número de estados.
Gramáticas sensibles al contexto
El primer problema conocido de PSPACE -completo fue el problema de palabras para gramáticas deterministas sensibles al contexto . En el problema de palabras para gramáticas sensibles al contexto, se le da un conjunto de transformaciones gramaticales que pueden aumentar, pero no disminuir, la longitud de una oración, y desea determinar si una oración dada podría producirse mediante estas transformaciones. La condición técnica del "determinismo" (que implica aproximadamente que cada transformación hace obvio que se utilizó) asegura que este proceso se puede resolver en el espacio polinomial, y Kuroda (1964) demostró que todo programa (posiblemente no determinista) computable en lineal el espacio podría convertirse en el análisis sintáctico de una gramática sensible al contexto, de una manera que preserve el determinismo. [3] 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.
Fórmulas booleanas cuantificadas
Hoy en día, el problema arquetípico de PSPACE-completo generalmente se considera el problema de fórmula booleana cuantificada (generalmente abreviado como QBF o TQBF; la T significa "verdadero"), una generalización del primer problema NP-completo conocido , el problema de satisfacibilidad booleano (SE SENTÓ). El problema de la satisfacibilidad es el problema de si hay asignaciones de valores de verdad a las variables que hacen que una expresión booleana sea verdadera. [4] Por ejemplo, una instancia de SAT sería la cuestión de si lo siguiente es cierto:
El problema de la fórmula booleana cuantificada se diferencia en permitir la cuantificación tanto universal como existencial sobre los valores de las variables:
- .
La prueba de que QBF es un problema completo de PSPACE es esencialmente una reafirmación de la prueba del teorema de Savitch en el lenguaje de la lógica, y es un poco más técnica.
Rompecabezas y juegos
El problema NP-completo de la sección anterior se asemeja a los acertijos típicos: ¿hay alguna forma de introducir valores que resuelva el problema? En consecuencia, el problema de PSPACE-complete se parece a los juegos: ¿hay algún movimiento que pueda hacer, de modo que para todos los movimientos que pueda hacer mi oponente, haya algún movimiento que pueda hacer para ganar? La pregunta alterna cuantificadores existenciales y universales. No es de extrañar que muchos acertijos resulten ser NP-completos y muchos juegos resulten ser completos para PSPACE. [5]
Ejemplos de juegos que son completos para PSPACE (cuando se generalizan para que se puedan jugar en un tablero n × n ) son los juegos Hex y Reversi, los juegos de solitario Rush Hour , Mahjong , Atomix y Sokoban , y la computadora mecánica Turing Tumble . Algunos otros juegos generalizados, como el ajedrez , las damas (borradores) y Go son EXPTIME-complete 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 -complete si se aplica un límite polinomial en el número de movimientos. [5]
Tenga en cuenta que la definición de completitud de PSPACE se basa en la complejidad asintótica : el tiempo que lleva resolver un problema de tamaño n , en el límite a medida que n crece sin límite. Eso significa que un juego finito como las damas (que se juega en un tablero de 8 × 8) nunca podría ser completo para PSPACE, ya que se pueden resolver en tiempo y espacio constantes usando una tabla de búsqueda muy grande (las damas ya se resuelven de esta manera) . Es por eso que todos los juegos se modificaron jugándolos en un tablero n × n ; en algunos casos, como en el caso del ajedrez, estas extensiones son artificiales.
Referencias
- ^ Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, pág. 92, ISBN 9781139477369
- ^ Hunt, HB, III (1973), "Sobre el tiempo y la complejidad de la cinta de los lenguajes. I", Quinto Simposio Anual ACM sobre Teoría de la Computación (Austin, Texas, 1973) , Assoc. Computación. Mach., Nueva York, págs. 10-19, MR 0421145
- ^ Kuroda, S.-Y. (1964), "Clases de lenguajes y autómatas delimitados linealmente", Información y Computación , 7 : 207–223, doi : 10.1016 / s0019-9958 (64) 90120-2 , MR 0169724
- ^ Garey, Michael R .; Johnson, David S. (1979), "Sección 7.4: Completitud del espacio polinomial", Computadoras e intratabilidad: Una guía para la teoría de NP-Completitud , WH Freeman, pp. 170-177 , ISBN 0-7167-1045-5
- ^ a b Eppstein, David , complejidad computacional de juegos y rompecabezas
Otras lecturas
- Sipser, Michael (1997), "Sección 8.3: Completitud de PSPACE", Introducción a la teoría de la computación , PWS Publishing, págs. 283-294 , ISBN 0-534-94728-X.