DSPACE
DSPACE という尺度は、あるメモリ空間量を使って解ける全ての決定問題の集合である複雑性クラスの定義に使われる。任意の関数 f(n) について、複雑性クラス SPACE(f(n)) があり、決定性チューリング機械で O(f(n)) の空間(領域)を使って解ける決定問題の集合を表す。この場合、計算にかかる時間に制限はないが、他の複雑性尺度は制限されることもある。
いくつかの重要な複雑性クラスが DSPACE を使って定義される。PSPACE は DSPACE を使って次のように定義される。
PSPACE = ⋃ k ∈ N DSPACE ( n k ) {\displaystyle {\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})}