PSPACE-complet

classe de complexitat

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:

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 modifica

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 modifica

  1. Michael,, Sipser,. Introduction to the theory of computation. Boston: PWS Pub. Co, 1997. ISBN 053494728X. 
  2. 2,0 2,1 Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  3. «Complexity Zoo:P - Complexity Zoo». Arxivat de l'original el 2018-01-19. [Consulta: 6 desembre 2018].
  4. «Computational Complexity of Games and Puzzles». [Consulta: 6 desembre 2018].