PSPACE-completo

En teoría de la complejidad computacional, la clase de complejidad PSPACE-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los problemas en PSPACE-completo pueden verse como los problemas más difíciles de la clase PSPACE. Se sospecha fuertemente que estos problemas están fuera de las clases de complejidad P y NP, pero no hay prueba de ello. Se sabe que no están contenidos en la clase NC.

El problema más básico de PSPACE-completo es el problema de las tautologías booleanas que es muy parecido a SAT salvo que se quiera saber si todas las asignaciones de variables de una expresión booleana hacen que la expresión sea cierta.

En teoría de complejidad, un problema de decisión es PSPACE-completo cuando pertenece a la clase de complejidad PSPACE y cada problema en PSPACE puede ser reducido a él en tiempo polinómico (véase completo (complejidad)). Puede pensarse que los problemas que son PSPACE-completos son los más difíciles de resolver en la clase PSPACE. Se sospecha ampliamente que estos problemas pueden estar fuera de las conocidas clases de complejidad P y NP, pero no es un hecho que haya sido demostrado. Sin embargo se tiene la certeza de que están fuera de NC.

Discusión

El primer problema NP-completo conocido fue el problema de satisfacción booleana (SAT). Este problema trata de descubrir si hay variables a las que al asignarle el valor verdadero convierten una expresión booleana en verdadera. Por ejemplo, una instancia del problema SAT sería preguntarse si la siguiente expresión es verdadera:

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

Se puede generalizar el problema SAT para el problema de la fórmula booleana cuantificada (QBF), un importante problema PSPACE-completo que permite una cuantificación tanto universal como existencial sobre el valor de las variables:

$\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})$

La demostración de que QBF es PSPACE-completo es esencialmente una reafirmación de la demostración del teorema de Savitch en el lenguaje de la lógica y es un poco más técnico. Hemos de destacar que los problemas NP-completos se parecen al típico puzle: ¿Existe alguna forma de insertar los valores que resuelve el problema? El problema PSPACE-completo, sin embargo se parece a un juego: ¿Hay algún movimiento que pueda yo hacer de manera que todos los movimientos posibles de mi oponente pudiera hacer me llevasen a poder hacer algún otro movimiento mío en el cual yo gane? La pregunta alterna cuantificadores existenciales con cuantificadores universales. No nos resulta sorprendente pues que muchos puzles resulten ser NP-completos y muchos juegos de tablero sean PSPACE-completos.

Algunos ejemplos de juegos que sean PSPACE-completos (cuando están generalizados de manera que se pueda jugar en un tablero de dimensión n x n) son los juegos hex y reversi y los juegos en solitario Solitario Mahjong, Atomix, Sokoban. Otros juegos generalizados como son el ajedrez, las damas o el go son problemas EXPTIME-completos.

Resaltaremos también que la definición de PSPACE-completitud está basada en la complejidad asintótica: el tiempo que tarda en resolverse un problema de tamaño n cuando n crece sin ningún límite. Esto quiere decir que un juego como las damas (que se juega en un tablero de 8 x 8) nunca podrá ser PSPACE-completo (de hecho, puede ser resuelto en un tiempo constante utilizando una enorme Lookup table). Este es el motivo por el cual todos los juegos han sido modificados para ser jugados en un tablero de n x n en lugar del tamaño original; en algunos casos tales como el ajedrez, estas extensiones resultan muy artificiales y subjetivas. Otro problema PSPACE-completo es el de decidir si una cadena de caracteres es miembro o no del lenguaje definido por una gramática sensible al contexto dada.

Ejemplos de problemas PSPACE-completos

A continuación se exponen algunos problemas con esbozos de algoritmos que muestran que pertenecen a PSPACE.

TQBF

Sea TQBF = { <F> : F es una fórmula booleana verdadera totalmente cuantificada }. De entrada F: Si F no tiene cuantificador, evalúa y acepta si y solo si F es verdadera. Si F=pF', evaluar recursivamente F'[p=1] y F'[p=0], aceptar si y solo si ambos la aceptan. Si F=qF', evaluar recursivamente F'[q=1], F'[q=0] y aceptar si y solo si al menos una la acepta. Consumo Espacial: El número de niveles recursivo es exactamente igual al número de variables de F. La cantidad de información almacenada en cada nivel de la recursión es constante (valores de la fórmula para p=0 y p=1). Por lo tanto el espacio total utilizado es lineal.

Estrategias Ganadoras Para Juegos

Véase Complejidad en los juegos para más juegos cuya completitud para PSPACE o cualquier otra clase de complejidad ha sido probada.

Geografía Generalizada

El problema de la Geografía Generalizada es un juego infantil similar a las palabras encadenadas pero empleando únicamente ciudades que deban empezar con el nombre de la anterior sin repetir ninguna. Con los datos de este problema podemos construir el grafo <G,b> del conjunto de ciudades relacionado por su letra inicial-final:

• Con entrada <G,b>:
  • Si b no tiene aristas salientes, se rechaza.
  • En otro caso, se elimina b y todas sus aristas, a este nuevo grafo se le llama G₁.
  • Recursivamente se ejecuta con entradas <G₁,b_i>, donde cada b_i son los nodos a los que apuntaban las aristas de b.
  • Se finaliza si se aceptan todas, en otro caso continúa el proceso.

Consumo Espacial: El número de niveles de la recursión será igual al número de nodos de G. La cantidad de información almacenada en cada nivel es también igual al número de nodos de G. Por lo tanto el consumo total del espacio es lineal.

Enlaces externos

• Complejidad computacional de Juegos y rompecabezas (en inglés)

• Datos: Q905967