PSPACE-complet

En teoria de la complexitat, la classe de complexitat PSPACE-Complet és la classe dels problemes de decisió que es poden resoldre amb un espai de memòria polinòmic respecte la mida de l'entrada i si tot problema que es pot resoldre en espai polinòmic es pot reduir a aquest en un temps polinòmic. Els problemes que son PSPACE-complet es poden veure com els problemes més difícils de la classe PSPACE.^[1][2]

L'exemple més conegut de problema dins de PSPACE-complet és el problema SAT. Una variant d'aquest problema, el conegut com el problema de la fórmula booleana qualificada verdadera (QBF o TQBF).^[3] Aquest problema consisteix en trobar:

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

Alguns problemes d'aquesta classe son semblants a jocs i la pregunta a respondre és del tipus "existeix algun moviment que un jugador pugui fer, tal que tots els moviments del seu adversari facin que el primer jugador pugui guanyar?". Hi ha força exemples de jocs i trencaclosques que entren dins aquesta classe de complexitat.^[4]

Relacions amb d'altres classes

Es creu que aquesta mena de problemes estan fora de les classes P i NP, però no s'ha pogut demostrar.

Se sap que PSPACE-complet està fora de la classe NC, perquè els problemes NC es poden resoldre en un espai polinòmic del logaritme de la mida de l'entrada i pel teorema de la jerarquia estan continguts dins de NC.^[2]

Referències