EXPSPACE

En teoria de la complexitat, la classe de complexita EXPSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(2^p(n)), on p(n) és una funció polinomial sobre n. D'acord amb el teorema de Savitch, aquesta classe és igual a la que considera màquines de Turing no deterministes. Quan es restringeix p(n) a una funció lineal, la classe resultant s'anomena ESPACE.^[1][2]

En termes de DSPACE es té

${\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})}$

La classe de complexitat EXPSPACE-complet és la classe de problemes que estan a EXPSPACE tals que tot problema d'EXPSPACE tenen una transformació polinòmica cap a cada un dels problemes d'EXPSPACE-complet. Dit d'una altra manera, existeix un algorisme que treballa en temps polinòmic que transforma les instàncies d'un problema en les instàncies de l'altra amb la mateixa resposta. El conjunt EXPSPACE-complet pot esser vist com el conjunt de problemes més difícils d'EXPSPACE.

EXPSPACE conté de manera estricta les classes PSPACE, NP-Complet, NP i P i es creu que també conté estrictament el conjunt EXPTIME.

El 1980, L. Berman va demostrar que el problema de verificar o falsar qualsevol expressió de primer ordre sobre els nombres reals que només utilitza suma i comparació però no multiplicació està a EXPSPACE.

Referències

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.