空間の複雑さ

アルゴリズムまたはデータ構造の空間複雑度とは、入力の特性に応じて計算問題のインスタンスを解決するために必要なメモリ空間の量です。これは、アルゴリズムが完全に実行されるまでに必要なメモリです。 ^{[ 1 ]}これには、入力が使用するメモリ空間（入力空間と呼ばれる）と、実行中に使用するその他の（補助）メモリ（補助空間と呼ばれる）が含まれます。

時間計算量と同様に、空間計算量も多くの場合、漸近的にビッグオー記法で表現されます。${\displaystyle O(n),}$${\displaystyle O(n\log n),}$${\displaystyle O(n^{\alpha }),}$${\displaystyle O(2^{n}),}$ここで、nは入力の特性であり、空間計算量に影響を与える。

時間計算量クラスDTIME(f(n))およびNTIME(f(n))と同様に、計算量クラスDSPACE(f(n))およびNSPACE(f(n))は、それぞれ決定論的（非決定論的）チューリングマシンによって決定可能な言語の集合であり、${\displaystyle O(f(n))}$空間。複雑性クラスPSPACEとNPSPACEは、${\displaystyle f}$PやNPと同様に、任意の多項式である。つまり、 $${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$ そして $${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

空間階層定理は、すべての空間構成可能関数について、${\displaystyle f(n),}$機械で解決できる問題が存在する${\displaystyle f(n)}$メモリ空間は、漸近的に以下のマシンでは解けない。${\displaystyle f(n)}$空間。

複雑性クラス間の以下の包含関係が成り立つ。^{[ 2 ]}$${\displaystyle {\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)}$$

さらに、サビッチの定理は、もし${\displaystyle f\in \Omega (\log(n)),}$$${\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).}$$

直接的な帰結として、${\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}.}$この結果は、非決定性によって問題解決に必要な空間がわずかにしか削減されないことを示唆しているため、驚くべきものである。対照的に、指数時間仮説は、時間計算量に関しては、決定論的計算量と非決定論的計算量の間に指数関数的な差が存在する可能性があると予測している。

インメルマン・シェレプセニイの定理は次のように述べています。${\displaystyle f\in \Omega (\log(n)),}$${\displaystyle {\mathsf {NSPACE}}(f(n))}$は補完関係の下で閉じている。これは、時間計算量クラスと空間計算量クラスの質的な違いを示している。非決定性時間計算量クラスは補完関係の下で閉じていないと考えられているからである。例えば、NP ≠ co-NPであると推測されている。^{[ 3 ] [ 4 ]}

L または LOGSPACE は、決定論的チューリングマシンが 1 つのデータのみを使用して解決できる問題の集合です。${\displaystyle O(\log n)}$入力サイズに関するメモリ空間。全体をインデックスできる単一のカウンタでさえ${\displaystyle n}$-ビット入力には${\displaystyle \log n}$スペースの関係上、LOGSPACEアルゴリズムは一定数のカウンタまたは同様のビット複雑度を持つその他の変数しか保持できません。

LOGSPACE やその他の準線形空間計算量は、コンピュータのRAMに収まらない大きなデータを処理する際に役立ちます。これらはストリーミング アルゴリズムに関連していますが、使用できるメモリ量を制限するだけで、ストリーミング アルゴリズムは入力がアルゴリズムにどのように供給されるかについてさらに制約があります。このクラスは、擬似乱数と非ランダム化の分野でも使用されており、研究者はL = RLかどうかという未解決問題を検討しています。^{[ 5 ] [ 6 ]}

対応する非決定性空間複雑度クラスはNLです。

用語補助空間とは、入力によって消費される空間以外の空間を指します。補助空間の複雑さは、別の入力テープチューリングマシン正式に定義できます。補助空間の複雑さは、作業テープを介して定義（および分析）されます。たとえば、バランスのとれた二分木の深さ優先探索う。${\displaystyle n}$ノード: その補助空間の複雑さは${\displaystyle \Theta (\log n).}$

• アルゴリズムの分析– アルゴリズムが使用するリソースの研究 
• 計算複雑性理論― 計算問題の本質的な難しさ 
• 計算資源― 計算複雑性理論の一側面 
• 時間計算量– アルゴリズムの実行にかかる時間の推定値