DSPACE

DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース︵プログラムの実行に必要な物理的メモリ量︶と直接対応することから、最もよく研究されている複雑性の尺度の1つである。

複雑性クラス

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

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

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

計算機械モデル

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

階層定理

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

一般化

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


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