PSPACE-completo

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.

Contenido

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 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \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 \or \neg x_3 \or x_4) \and (\neg x_2 \or x_3 \or \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 formula booleana verdadera totalmente cuantificada }. De entrada F: Si F no tiene cuantificador, evalua 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 G1.
    • Recursivamente se ejecuta con entradas <G1,bi>, donde cada bi 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


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • PSPACE — En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial ( ) y tiempo ilimitado. La definición no depende del… …   Wikipedia Español

  • ESPACIOP-completo — En teoría de la complejidad computacional, la clase de complejidad ESPACIOP completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en ESPACIOP y todo problema en ESPACIOP puede ser reducido a él en tiempo polinomial.… …   Enciclopedia Universal

  • Complejidad en los juegos — Este artículo o sección sobre ocio necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 11 de junio de 2008. También puedes ayudar… …   Wikipedia Español

  • EXPTIME — En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una… …   Wikipedia Español

  • Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

  • Anexo:Clases de complejidad — Esta es la lista de clases de complejidad en teoría de la complejidad computacional. Muchas de estas clases tienen una co clase que contiene los problemas complementarios a los de la clase original. Por ejemplo, si L está en NP, el complemento de …   Wikipedia Español

  • Clases de complejidad — Anexo:Clases de complejidad Saltar a navegación, búsqueda Esta es la lista de clases de complejidad en teoría de la complejidad computacional. Muchas de estas clases tienen una co clase que contiene los problemas complementarios a los de la clase …   Wikipedia Español

  • Transformación polinómica — En complejidad computacional, una transformación polinomial, reducción polinomial o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza… …   Wikipedia Español

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • Lenguaje sensible al contexto — En las ciencias de la computación, un lenguaje sensible al contexto es un [[lenguaje formal] que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”