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.