En teoria de la complexitat, la classe de complexitat DSPACE(f(n)) o SPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida determinista de la classe NSPACE.[1][2]
Diverses classe de complexitat es defineixen en funció de DSPACE:
- REG = DSPACE(O(1)).
- L = DSPACE(O(log n))
- PSPACE =
- EXPSPACE =
Relació amb d'altres classes
DSPACE és la contrapart determinística de NSPACE, la classe en espai de memòria amb màquines de Turing no determinista. Pel teorema de Savitch, es te:
NTIME està relacionada amb DSPACE de la següent manera: sigui t(n) una funció construïble, es te:
Referències
- ↑ 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.
Classes de complexitat |
---|
Considerades tractables | DLOGTIME · AC0 · ACC0 · TC0 · L · SL · RL · NL · NC · SC · CC · P · P-complet · ZPP · RP · BPP · BQP · APX |
---|
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 | |
---|