計算複雑性理論：計算問題に必要な時間・空間・計算量クラス

基本的な尺度と記法

最も一般的な資源は、時間計算量（アルゴリズムが要する基本ステップ数）と、空間計算量（必要とする記憶領域）である。O記法、Θ記法、Ω記法などの漸近記法は、大きな入力に対する増加率を表すために用いられる。ほかの尺度には、乱数性（必要なランダムビット数）、通信（当事者間で交換しなければならない情報量）、並列計算における回路サイズや回路深さがある。

計算量クラスと代表例

• P：決定性機械により多項式時間で解ける問題。一般に効率よく解けると見なされる。
• NP：解が多項式時間で検証できる問題。多くの自然な組合せ問題を含む。
• PSPACE、EXPなど：多項式空間や指数時間といった、より大きな資源上限によって定義されるクラス。

計算複雑性理論は、完全性と困難性も研究対象とする。ある問題がクラス完全であるとは、そのクラス内で最も難しい問題群に属することを意味する。帰着は、ある問題のインスタンスを別の問題のインスタンスへ写し、困難性の結果を移すとともに、問題を階層として整理する。

歴史と計算モデル

この分野は、計算とアルゴリズムに関する初期の研究から発展した。チューリング機械、ランダムアクセス機械（RAM）、ブール回路などの形式的モデルは、資源使用量を厳密に定義する方法を提供する。1960年代と1970年代の基礎的な成果によって、NP完全性などの中心概念が確立され、問題に効率的な解法が存在しそうにないことを示す技法が導入された。背景知識については入門的な概説、または教育用サイトの教科書や講義ノートを参照できる。

用途と重要性

計算複雑性理論は実践的な分野にも影響を与える。効率的な手法へアルゴリズム設計者を導き、セキュリティをもたらす困難な問題を特定することで暗号理論を支え、最適化やスケジューリングに対する現実的な見通しを与える。最悪ケースの上界を知ることは性能に関する保証をもたらし、平均ケース解析や償却解析は典型的な挙動または長期的な挙動を記述する。

区別と未解決問題

複雑性は計算可能性とは異なる。問題は計算可能であっても、実用的でないほど多くの資源を必要とする場合がある。中心的な問いの多くはいまだ未解決であり、最も有名なのはPとNPが等しいかという問題である。これは、効率よく検証できるあらゆる解が、効率よく見つけられるかを問う未解決問題である。さらに、乱数性（BPP）、近似アルゴリズム、パラメータ化計算量、量子計算量を含む新たなモデルについても研究が進められている。追加の文献や資料は選定された文献目録を参照できる。