PSPACE
En teoria de la complexitat, la classe de complexitat PSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing usant un espai polinòmic.[1][2]
Definició formal
[modifica]Si anotem amb SPACE(t(n)) el conjunt de tots els problemes que es poden resoldre amb una màquina de Turing usant O(t(n)) d'espai per alguna funció t de la mida de l'entrada n, llavors es pot definir PSPACE com
PSPACE és un superconjunt estricte del conjunt de llenguatges sensibles al context.
Resulta que fent que la màquina de Turing sigui no determinista no afegeix cap potència extra. Donat el teorema de Savitch, NPSPACE és equivalent a NSPACE, bàsicament perquè una màquina de Turing determinista pot simular una de no determinista sense que li calgui més espai, tot i que pot tardar molt més temps. També, el complementari de tots els problemes de PSPACE estan a PSPACE, fent que PSPACE-complementari = PSPACE.
Relació amb d'altres classes
[modifica]![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/6e/Complexity_subsets_pspace.svg/220px-Complexity_subsets_pspace.svg.png)
Les següents relacions son conegudes entre PSPACE i les classes de complexitat NL, P, NP, PH, EXPTIME i EXPSPACE (⊊ vol dir conté estricte, i no és el mateix que ⊈):
De les dues primeres línies se sap que almenys un dels conjunts conté estrictament un altre, però no se sap quin. Se suposa que tots ho son.
Referències
[modifica]- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
- ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
Considerades tractables | |
---|---|
Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
Considerades intractables | |
Jerarquia de classes | |
Families de classes |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.