DSPACE

DSPACEと計算複雑性理論

DSPACE及びSPACEは、計算複雑性理論において重要な概念であり、特に決定性チューリング機械による計算におけるメモリ使用量を示す指標です。これらは、特定のアルゴリズムが問題を解く際に必要とする空間的リソースの量を評価します。実際の計算資源を考慮に入れるため、DSPACEは最もよく研究されている複雑性尺度の一つです。

複雑性クラス

DSPACEの概念は、メモリ空間の制約のもとで解ける全ての決定問題の集合を定義する際に活用されます。任意の関数f(n)に対して、SPACE(f(n))という複雑性クラスが設けられており、これは決定性チューリング機械がO(f(n))の空間を使って解決可能な決定問題の集合を表現します。このクラスは、計算に要する時間に制限は示されていませんが、他の複雑性尺度とは異なり、空間の制約に特化しています。中でも、PSPACEというクラスは、DSPACEを用いて明確に定義されています。

$$
PSPACE = igcup_{k ext{ ∈ } ext{N}} DSPACE(n^k)
$$

計算機械モデル

DSPACEは通常、決定性チューリング機械を基にした指標です。いくつかの空間的複雑性クラスは準線形であり、必要とされる領域が入力サイズよりも小さいことが特徴です。この特性を理解するためには、入力専用のテープと出力専用のテープを持ち、作業用のテープの使用量が実際のメモリの消費を反映する複数テープのチューリング機械のモデルを考えることが有用です。これにより、L（対数領域）と呼ばれる小規模な空間的複雑性クラスも定義されます。

階層定理

領域階層定理は、任意の構成可能な領域関数fに対し、特定の言語Lが次のように示されることを述べています。:

• - 領域O(f(n))では判定が可能である一方で、領域o(f(n))では判定が不可能となる言語が存在するということです。これにより、計算問題の難易度を空間の制約によって評価する枠組みが提供されます。

NSPACEとの関係

DSPACEには対になる概念としてNSPACEが存在し、これは非決定性チューリング機械におけるメモリ空間のクラスを示します。サヴィッチの定理により、以下のような関係が成り立ちます。

$$
DSPACE[s(n)] ⊆ NSPACE[s(n)] ⊆ DSPACE[(s(n))^2]
$$

これにより、決定性および非決定性の観点からの空間的リソースの関係性が明確化され、計算複雑性理論の基盤が一層強化されているのです。

もう一度検索