計算複雑性理論
ある量の計算資源を使って解くことができるすべての計算問題の集合を複雑性クラスという。
複雑性クラス P は、チューリング機械で多項式時間で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である。
複雑性クラス NP は、非決定性チューリング機械で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、充足可能性問題、ハミルトン閉路問題、頂点被覆問題などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ。
多くの複雑性クラスは、それを表現するのに必要となる論理体系によって特徴付けられる。これは、記述計算量の概念と関係がある。
各クラスに対し、そのクラスの完全問題を考えることがある。クラスCの完全問題とはCに属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。