DSPACE

DSPACE という尺度は、あるメモリ空間量を使って解ける全ての決定問題の集合である複雑性クラスの定義に使われる。任意の関数 f(n) について、複雑性クラス SPACE(f(n)) があり、決定性チューリング機械で O(f(n)) の空間（領域）を使って解ける決定問題の集合を表す。この場合、計算にかかる時間に制限はないが、他の複雑性尺度は制限されることもある。

いくつかの重要な複雑性クラスが DSPACE を使って定義される。PSPACE は DSPACE を使って次のように定義される。

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

DPSACE は一般に決定性チューリング機械上の尺度である。いくつかの重要な空間複雑性クラスは準線形、すなわち必要な領域が入力サイズより小さい。従って、入力のサイズや出力のサイズを除外しないと、あるアルゴリズムが使用する真のメモリ空間量はわからない。このためのモデルとして複数のテープを持つチューリング機械があり、入力専用で書き込まれることがないテープと出力専用で読み込まれることがないテープを持ち、それら以外の作業用テープの使用領域がメモリ使用量となる。このようなモデルを想定することで、L（対数領域）のような小さな空間複雑性クラスが定義できる。

領域階層定理（英語版）によれば、全ての領域構成可能関数 ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ について言語 L が存在して、領域 ${\displaystyle O(f(n))}$ では判定可能だが、領域 ${\displaystyle o(f(n))}$ では判定不能である。

DSPACE と対になる概念として NSPACE がある。NSPACE は非決定性チューリング機械におけるメモリ空間のクラス（の記法）である。サヴィッチの定理によれば、次のような関係が成り立つ。

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