DSPACE
DSPACE と対になる概念として NSPACE がある。NSPACE は非決定性チューリング機械におけるメモリ空間のクラス(の記法)である。サヴィッチの定理によれば、次のような関係が成り立つ。
DSPACE [ s ( n ) ] ⊆ NSPACE [ s ( n ) ] ⊆ DSPACE [ ( s ( n ) ) 2 ] . {\displaystyle {\mbox{DSPACE}}[s(n)]\subseteq {\mbox{NSPACE}}[s(n)]\subseteq {\mbox{DSPACE}}[(s(n))^{2}].}
DPSACE は一般に決定性チューリング機械上の尺度である。いくつかの重要な空間複雑性クラスは準線形、すなわち必要な領域が入力サイズより小さい。従って、入力のサイズや出力のサイズを除外しないと、あるアルゴリズムが使用する真のメモリ空間量はわからない。このためのモデルとして複数のテープを持つチューリング機械があり、入力専用で書き込まれることがないテープと出力専用で読み込まれることがないテープを持ち、それら以外の作業用テープの使用領域がメモリ使用量となる。このようなモデルを想定することで、L(対数領域)のような小さな空間複雑性クラスが定義できる。