DSPACE

計算複雑性理論において、DSPACEまたはSPACEは、決定論的チューリングマシンのメモリ空間のリソースを表す計算リソースです。これは、「通常の」物理コンピュータが特定のアルゴリズムを用いて特定の計算問題を解決するために必要とするメモリ空間の総量を表します。

DSPACE尺度は、特定のメモリ空間を使用して解決できるすべての決定問題の集合である複雑性クラスを定義するために使用されます。各関数f ( n ) に対して、決定性チューリングマシンが空間O ( f ( n ) ) を使用して解決できる決定問題の集合である複雑性クラスSPACE( f ( n )) が存在します。使用できる計算時間の量に制限はありませんが、他の複雑性尺度 (交代など) には制限がある場合があります。

DSPACEの観点から、いくつかの重要な複雑性クラスが定義されています。これらには以下が含まれます。

• REG = DSPACE( O (1))、ここでREGは正規言語のクラスです。実際には、REG = DSPACE( o (log  log n )) (つまり、非正規言語を認識するにはΩ(log log n )の空間が必要です)。 ^{[ 1 ] [ 2 ]}   

証明：s ( n ) = o (log log n )に対して、 非正規言語L ∈ DSPACE( s ( n )) が存在すると仮定する。空間s ( n ) においてL を決定するチューリングマシンをMとする。仮定によりL ∉ DSPACE( O (1)) であるため、任意の任意の に対して、${\displaystyle k\in \mathbb {N} }$入力Mにはkよりも多くのスペースを必要とするものがある。

x をkよりも多くのスペースを必要とする最小サイズの入力 (n で表される) とし、$\displaystyle {\mathcal {C}}}$を入力xに対するMのすべての構成の集合とする。M ∈ DSPACE( s ( n ))であるため、$\displaystyle |{\mathcal {C}}|\leq 2^{c\cdot s(n)}=o(\log n)}$ここで、cはMに依存する定数である。

S を、Mのx上での可能なすべての交差列の集合とする。M のx上での交差列の長さは最大で であることに注意する。${\displaystyle |{\mathcal {C}}|}$: それより長い場合は、何らかの構成が繰り返され、M は無限ループに陥ります。また、最大で${\displaystyle |{\mathcal {C}}|}$交差列の各要素には可能性があるので、 x上のMの異なる交差列の数は

${\displaystyle |S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c\cdot s(n)})^{2^{c\cdot s(n)}}=2^{c\cdot s(n)\cdot 2^{c\cdot s(n)}}<2^{2^{2c\cdot s(n)}}=2^{2^{o(\log \log n)}}=o(n)}$

鳩の巣原理によ​​れば、次のようなインデックスi < jが存在する。${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$、 どこ${\displaystyle {\mathcal {C}}_{i}(x)}$そして${\displaystyle {\mathcal {C}}_{j}(x)}$は、それぞれ境界iおよびjにおける交差シーケンスである。

x' を、 xからi + 1からjまでのすべてのセルを削除して得られる文字列とする。機械M は入力x'に対しても入力xに対しても全く同じように動作するため、 x' を計算するのに必要な空間はx を計算するのに必要な空間と同じである。しかし、| x' | < | x |であり、これはxの定義に矛盾する。したがって、想定したような言語L は存在しない。□

上記の定理は、空間階層定理における空間構成可能関数の仮定の必要性を示唆している。

• L = DSPACE( O (log n )) 
• PSPACE =${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• エクスプスペース=${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

DSPACE は従来、決定論的チューリングマシン上で測定されます。重要な空間複雑性クラスのいくつかは準線形、つまり入力サイズよりも小さいです。したがって、アルゴリズムに入力サイズまたは出力サイズを「課金」しても、実際に使用されるメモリ空間を正確に捉えることはできません。この問題は、入力と出力を持つマルチテープチューリングマシンを定義することで解決されます。これは、入力テープへの書き込みが不可能で、出力テープからの読み出しが不可能な点を除いて、標準的なマルチテープチューリングマシンです。これにより、L (対数空間) などのより小さな空間クラスを、すべての作業テープ (特別な入力テープと出力テープを除く) が使用する空間の量に基づいて定義できます。

アルファベットの適切なべき乗を取ることで多くの記号を1つにまとめることができるため、c ≥ 1かつf ( n ) ≥ 1を満たすすべてのfに対して、 cf ( n ) 空間で認識可能な言語のクラスはf ( n ) 空間で認識可能な言語のクラスと同じになります。このことから、定義においてビッグオー記法を使用することが正当化されます。

空間階層定理は、すべての空間構成可能関数に対して、${\displaystyle f:\mathbb {N} \to \mathbb {N} }$空間的に決定可能な言語Lが存在する${\displaystyle O(f(n))}$しかし宇宙空間ではそうではない${\displaystyle o(f(n))}$。

DSPACEは、非決定性チューリングマシン上のメモリ空間クラスであるNSPACEの決定性対応物である。サビッチの定理^{[ 3 ]}によれば、

${\displaystyle {\mathsf {DSPACE}}(s(n))\subseteq {\mathsf {NSPACE}}(s(n))\subseteq {\mathsf {DSPACE}}{\bigl (}(s(n))^{2}{\bigr )}.}$

NTIMEはDSPACEと以下の関係にある。任意の時間構成可能関数t ( n )に対して、

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$。

決定論的時間については、はるかに優れたシミュレーションが知られています。${\displaystyle t(n)\geq n}$、

${\displaystyle {\mathsf {DTIME}}(t(n))\subseteq {\mathsf {DSPACE}}\left({\sqrt {t(n)\log t(n)}}\right)}$

ウィリアムズ^{[ 4 ]}の結果として、古い境界を改善し、${\displaystyle O(t/\log t)}$ホップクロフト、ポール、ヴァリアントによる。^{[ 5 ]}

一方、任意の関数に対して$\displaystyle s(n)\geq \log n}$、

${\displaystyle {\mathsf {DSPACE}}(s(n))\subseteq {\mathsf {DTIME}}{\bigl (}2^{O(s(n))}{\bigr )}}$。

• Szepietowski, Andrzej (1994).チューリングマシンと劣対数空間. Springer Science+Business Media . ISBN 978-3-540-58355-4。
• Arora, Sanjeev ; Barak, Boaz (2009).計算複雑性。現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4. Zbl 1193.68112 . 

• 複雑性動物園: DSPACE( f ( n ))。