Hay un buen paralelismo entre NP-complete y PSPACE-complete.
Sea phi una fórmula booleana en forma conjuntiva normal. http://en.wikipedia.org/wiki/Con…
Juega un pequeño juego de rompecabezas en el que asignas un valor a x_1, luego a x_2, y así hasta que hayas asignado todas las variables. Si conecta estos valores en phi satisfactorio, ¡entonces gana! Este es el problema NP-completo SAT.
- ¿Cuáles son buenos temas para un trabajo de investigación?
- ¿Cuáles son las áreas fascinantes de la informática? ¿Cuáles son algunas de las áreas más avanzadas técnicamente de la informática?
- Cómo encontrar un tema de investigación en informática adecuado para estudiantes universitarios
- ¿Qué startups de aprendizaje automático tienen más probabilidades de convertirse en empresas multimillonarias?
- ¿Quiénes son los informáticos más inspiradores y cómo se siente conocerlos?
Aparece tu rival, y es hora de un nuevo juego. Tú, Ash, asigna un valor a x_1. Luego, Gary asigna (antagónicamente) un valor a x_2. Continúe alternando hasta que se asignen todas las variables. Si estos valores satisfacen phi, ¡ganas! Este es el problema QBF completo de PSPACE.
PSPACE es una de las clases de complejidad más robustas, lo que significa que es muy incluyente, por ejemplo, el resultado reciente QIP = PSPACE. Por esta razón, creo que es difícil encontrar ejemplos “sorprendentes” de problemas completos de PSPACE. Puede haber algunos ejemplos donde la alternancia es sutil y oculta, no estoy seguro.
