DSPACEのソースを表示

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

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

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

:<math>\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(n^k)</math>

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

== 階層定理 ==
{{仮リンク|領域階層定理|en|Space hierarchy theorem}}によれば、全ての[[構成可能関数|領域構成可能関数]] <math>f: \mathbb{N} \to \mathbb{N}</math> について言語 L が存在して、領域 <math>O(f(n))</math> では判定可能だが、領域 <math>o(f(n))</math> では判定不能である。<!-- 詳しくは[[領域階層定理]]を参照されたい。-->

== 一般化 ==
'''DSPACE''' と対になる概念として '''[[NSPACE]]''' がある。NSPACE は[[非決定性チューリング機械]]におけるメモリ空間のクラス（の記法）である。[[サヴィッチの定理]]によれば、次のような関係が成り立つ。
<blockquote>
<math>\mbox{DSPACE}[s(n)] \subseteq \mbox{NSPACE}[s(n)] \subseteq \mbox{DSPACE}[(s(n))^2].</math>
</blockquote>

{{複雑性クラス}}

[[Category:複雑性クラス]]
[[Category:計算資源]]
[[Category:数学に関する記事]]