計算量クラスとは？時間・空間などの資源で問題を分類する概念

形式的な考え方

形式的には、クラスは計算モデル（多くの場合はチューリング機械）と漸近的な資源制約に相対して定義される。たとえば、P は決定性チューリング機械で多項式時間で解ける決定問題の集合を表し、PSPACE は多項式空間で解ける問題を含む。定義では通常、最悪の場合の解析と漸近記法が用いられ、単一の入力例ではなく、大きな入力に対する振る舞いを捉える。

代表的なクラスと例

• P — 効率的な決定性多項式時間アルゴリズム。
• NP — 解の検証を多項式時間で行える問題。多くの自然な組合せ問題を含む。
• co-NP、PSPACE、EXPTIME — 資源制約や補集合によって定義される、より大きなクラス。
• BPP や RP のような確率的クラス、L や NL のような空間制約付きクラス。

中心的な概念の一つが還元である。ある問題の各入力を効率よく変換できるなら、その問題は別の問題と比べて少なくとも同程度に難しいとみなせる。還元はクラスごとの完全問題につながり、たとえば多くの自然な問題がNP完全であることが知られている。1970年代初頭のNP完全性の発見は、難しい問題の広い族をどのように分類できるかを示した。

役割と意義

計算量クラスは理論と実践の双方を形づくる。アルゴリズム設計の指針となり、暗号の仮定を支え、ヒューリスティック手法や近似手法が必要になる場面を示してくれる。多くの根本問題は未解決であり、最も有名なのはPとNPが等しいかどうかである。これは、解をすばやく検証できる問題は、すべてすばやく解けるのかを問う。

補足

計算量理論では、階層や分離といったクラス間の関係、補集合やオラクルアクセスのような操作に対する閉包性が研究される。入門や概説については、理論計算機科学の概要、数学的基礎の背景、還元と完全性に関する詳細な概説を参照するとよい。