目次
DSPACE
DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース（プログラムの実行に必要な物理的メモリ量）と直接対応することから、最もよく研究されている複雑性の尺度の1つである。
非決定性チューリングマシン
非決定性チューリング機械（ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。
複雑性クラス
複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
PSPACE
PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合 ^*、あるいは ^*の部分集合からへの写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。
見る NSPACEと決定問題
参考情報
複雑性クラス
- Co-NP
- DSPACE
- DTIME
- E (計算複雑性理論)
- ELEMENTARY
- ESPACE
- EXPSPACE
- EXPTIME
- L (計算複雑性理論)
- LOGCFL
- NC (計算複雑性理論)
- NEXPTIME
- NL (計算複雑性理論)
- NP
- NP困難
- NP完全問題
- NSPACE
- NTIME
- P (計算複雑性理論)
- PH (計算複雑性理論)
- PR (計算複雑性理論)
- PSPACE
- R (計算複雑性理論)
- RE (計算複雑性理論)
- SL (計算複雑性理論)
- UP (計算複雑性理論)
- 多項式時間近似スキーム
- 多項式階層
- 算術的階層
- 複雑性クラス