空間複雑性

Computer memory needed by an algorithm

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

時間の計算量と同様に、空間の計算量は、 などのように、大文字のO表記法で漸近的に表現されることが多く、ここでnは空間の計算量に影響を与える入力の特性です。 ${\displaystyle O(n),}$ ${\displaystyle O(n\log n),}$ ${\displaystyle O(n^{\alpha }),}$ ${\displaystyle O(2^{n}),}$

空間複雑度クラス

時間計算量クラスDTIME(f(n))およびNTIME(f(n))と同様に、計算量クラスDSPACE(f(n))およびNSPACE(f(n))は、空間を用いる決定性チューリングマシン（それぞれ非決定性チューリングマシン）によって決定可能な言語の集合である。計算量クラスPSPACEおよびNPSPACE は、 PおよびNPと同様に、任意の多項式を許容する。すなわち、 ${\displaystyle O(f(n))}$ ${\displaystyle f}$ $${\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}}.}$

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

ログスペース

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

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

対応する非決定論的空間計算量クラスはNLです。

補助空間の複雑さ

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

参照

• アルゴリズムの分析 – アルゴリズムで使用されるリソースの研究
• 計算複雑性理論 – 計算問題の本質的な難しさ
• 計算リソース – 処理手順やメモリなど、コンピュータが問題を解決するために必要なもの
• 時間計算量 – アルゴリズムの実行にかかる時間の見積もり

参考文献

1. Kuo, Way; Zuo, Ming J. (2003)、最適信頼性モデリング：原理と応用、John Wiley & Sons、p. 62、ISBN 9780471275459
2. Arora, Sanjeev ; Barak, Boaz (2007)、「計算複雑性：現代的アプローチ」（PDF）（草稿版）、p. 76、ISBN 9780511804090
3. イマーマン、ニール(1988)、「非決定性空間は相補性の下で閉じている」(PDF)、SIAM Journal on Computing、17 (5): 935– 938、doi :10.1137/0217058、MR  0961049
4. Szelepcsényi、Róbert ( 1987)、「非決定性オートマトンの強制方法」、EATCS の会報、33 : 96–100
5. Nisan, Noam (1992)、「RL ⊆ SC」、第24回ACMコンピューティング理論シンポジウム（STOC '92）の議事録、ビクトリア、ブリティッシュコロンビア、カナダ、pp.  619– 623、doi : 10.1145/129712.129772、ISBN 0-89791-511-9、S2CID  11651375{{citation}}: CS1 maint: location missing publisher (link)。
6. Reingold, Omer ; Trevisan, Luca ; Vadhan, Salil (2006)、「正則有向グラフ上の擬似ランダムウォークとRL対L問題」(PDF)、STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing、ニューヨーク: ACM、pp.  457– 466、doi :10.1145/1132516.1132583、ISBN 1-59593-134-1、MR  2277171、S2CID  17360260

Retrieved from "https://en.wikipedia.org/w/index.php?title=Space_complexity&oldid=1323512846"