DSPACE (Complexitat)

Enteoria de la complexitat,laclasse de complexitatDSPACE(f(n)) o SPACE(f(n)) és el conjunt delsproblemes de decisióque poden ser resolts amb unamàquina de Turing deterministaen espaiO(f(n)) i temps il·limitat. Es la contrapartida determinista de la classeNSPACE.

Diverses classe de complexitat es defineixen en funció de DSPACE:

• REG= DSPACE(O(1)).
• L= DSPACE(O(log n))
• PSPACE=${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• EXPSPACE=${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

Relació amb d'altres classes

DSPACE és la contrapart determinística de NSPACE, la classe en espai de memòria ambmàquines de Turing no determinista.Pelteorema de Savitch,es te:

${\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}]}$

NTIMEestà relacionada amb DSPACE de la següent manera: siguit(n)unafunció construïble,es te:

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$