PSPACE

classe de complexitat

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

 
Una representació de la relació entre classes de complexitat

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

  1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.