PSPACE-complet
Enteoria de la complexitat,laclasse de complexitatPSPACE-Completés la classe delsproblemes de decisióque es poden resoldre amb unespai de memòriapolinòmicrespecte 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 laclasse PSPACE.[1][2]
L'exemple més conegut de problema dins de PSPACE-complet és el problemaSAT.Una variant d'aquest problema, el conegut com el problema de lafó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 lesclasses PiNP,però no s'ha pogut demostrar.
Se sap que PSPACE-complet està fora de laclasse NC,perquè els problemes NC es poden resoldre en un espai polinòmic del logaritme de la mida de l'entrada i pelteorema de la jerarquiaestan continguts dins de NC.[2]
Referències
[modifica]- ↑Michael,,Sipser,.Introduction to the theory of computation.Boston: PWS Pub. Co, 1997.ISBN 053494728X.
- ↑2,02,1Sanjeev.,Arora,.Computational complexity: a modern approach.Cambridge:Cambridge University Press,2009.ISBN 9780521424264.
- ↑«Complexity Zoo:P - Complexity Zoo». Arxivat de l'originalel 2018-01-19. [Consulta: 6 desembre 2018].
- ↑«Computational Complexity of Games and Puzzles». [Consulta: 6 desembre 2018].
| Considerades tractables | |
|---|---|
| Suposadament intractables | |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
