DSPACE

デジタルリポジトリについては「DSpace」をご覧ください。

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

複雑性クラス

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}].}$

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ