Revisión del 20:29 1 jun 2009 editar CabreraDominguezYGarcia (discusión · contribs.) 8 ediciones mSin resumen de edición ← Ir a diferencia anterior		Revisión del 14:36 22 jun 2009 editar deshacer Muro Bot (discusión · contribs.) 1 375 372 ediciones m Bot: Arreglando encabezados (PR:CW); cambios cosméticos Ir a siguiente diferencia →
Línea 3: El problema más básico de PSPACE-completo es el problema de las tautologías booleanas que es muy parecido a [[Problema de satisfacibilidad booleana\|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 [[Complejidad computacional\|teoría de complejidad]], un [[problema de decisión]] es PSPACE-completo cuando pertenece a la [[ESPACIOP\|clase de complejidad PSPACE]] y cada problema en PSPACE puede ser reducido a él en tiempo polinómico (véase [[Complejidad computacional\|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: : <math>\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)</math> 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: : <math>\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)</math> 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. Línea 17: Otro problema PSPACE-completo es el de decidir si una cadena de caracteres es miembro o no del lenguaje definido por una [[Gramáticas sensibles al contexto\|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. Línea 26: 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 numero 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>: Línea 38: == Enlaces externos == [http://www.ics.uci.edu/~eppstein/cgt/hard.html Complejidad computacional de Juegos y rompecabezas] (en inglés) [[Categoría:Clases de complejidad]]

Diferencia entre revisiones de «PSPACE-completo»