計算量理論は、計算問題を解くのに必要な資源を分析する理論計算機科学の一分野である。アルゴリズムが使う時間、メモリ、その他の資源が入力サイズの増加に伴ってどのように増えるかを問い、最良の場合の資源境界に基づいて問題をクラスに分類する。この分野は、計算の数学的モデルと、実用上の実現可能性や効率性に関する関心を結びつける。
基本的な尺度と記法
最もよく用いられる尺度は、時間計算量（アルゴリズムが使う計算手順の数）と空間計算量（必要とする作業用メモリの量）である。O(·)、Ω(·)、Θ(·)のような漸近記法は、大きな入力に対する増大率を表し、機械固有の細部に依存せずにアルゴリズムを比較できる。形式的定義に用いられる標準的な計算モデルには、チューリング機械、ランダムアクセス機械、組合せ回路がある。
中心的概念とクラス
計算量理論は、資源境界を反映するクラスに問題を整理する。代表的なクラスには次がある:
- P: 多項式時間で解ける問題。しばしば扱いやすい、あるいは効率的に解けるとみなされる。
- NP: 解が多項式時間で検証できる問題。多くの重要な決定問題を含む。
- PSPACE: 時間にかかわらず、多項式空間で解ける問題。
- BPP のような確率的クラスや、NL、L のような非決定性空間クラス。
これらのクラスの中には、NP完全問題のような特別な種類の問題がある。これは効率的な還元の下でNPの中で最も難しい問題である。もしNP完全問題のどれか一つでも多項式時間で解ければ、NPのすべての問題が多項式時間で解けることになる。
手法、還元、困難性
中心的な手法には還元がある。これは、資源境界内での解けるかどうかを保ったまま、一つの問題を別の問題へ変換する方法である。また、対角化は、より多くの資源を必要とする問題を構成することでクラスを分離する。完全性や困難性の結果では、還元を用いて代表的な問題を特定する（たとえば充足可能性問題は、NP完全の典型例である）。こうした方法は、なぜ一部の問題が効率的なアルゴリズムに抵抗するのかを示し、実際に計算可能なことの限界を明らかにする。
歴史と意義
この分野は、計算可能性に関する初期の研究と、アルゴリズムの形式的定義から発展した。1970年代初頭の画期的な成果により、NP完全性の重要性が確立され、異なる問題どうしが還元によって結び付けられた。計算量理論はコンピュータ科学全体に深い影響を与え、暗号、最適化、アルゴリズム設計、時間とメモリの実用的なトレードオフの理解に役立っている。
応用と未解決問題
計算量理論は、実際のアルゴリズム選択を導き、近似法やランダム化手法が適切な場面を明確にし、計算上の本質的な障壁を説明する。最も有名な未解決問題の一つであるP = NP かどうかは、解を速く検証できる問題がすべて速く解けるのかを問う。この問題と、計算量クラス間の他の未解決な関係は、理論的にも実用的にも重要な研究課題であり続けている。
理論的基礎とアルゴリズム解析についてさらに読むには、理論計算機科学の入門書や総説を参照するとよい。あわせて、コンピュータ科学の概説や、アルゴリズムと計算量に関する詳しい解説も参照されたい。