DSPACE (Complexitat)

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.

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

• REG = DSPACE(O(1)).
• L = DSPACE(O(log n))
• PSPACE = $\bigcup _{k\in \mathbb{N}}𝖣𝖲𝖯𝖠𝖢𝖤(n^k)$
• EXPSPACE = $\bigcup _{k\in \mathbb{N}}𝖣𝖲𝖯𝖠𝖢𝖤(2^{n^k})$

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:

$𝖣𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤[s(n)]\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤[(s(n){)}^2]$

NTIME està relacionada amb DSPACE de la següent manera: sigui t(n) una funció construïble, es te:

$𝖭𝖳𝖨𝖬𝖤(t(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(t(n))$