複雑性クラス

複雑性クラス（ふくざつせいクラス、英: Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。

抽象機械 M によりO(f(n))の計算資源 R を使って解く事が出来る問題の集合（nは入力長）

例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。ここで、領域とは、実世界ではメモリ空間、チューリングマシンではテープの長さと考えればよい。一部の複雑性クラスは函数問題の集合である（例えばFP）。

数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。

ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。

複雑性クラス間の関係

以下の表はいくつかの問題（または文法、言語）のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。

		決定問題
Type 0 （帰納的可算）				決定不能
決定可能
EXPSPACE
EXPTIME
PSPACE
Type 1 （文脈依存）							PSPACE完全
		Co-NP				NP
			BPP		BQP		NP完全
		P
	NC						P完全
Type 2 （文脈自由）
Type 3 （正規）

複雑性クラス一覧

以下の一覧の各複雑性クラスには補問題の集合である 'Co' の付くクラスが存在する。例えば、問題 L が NP に含まれるなら、その補問題は Co-NP に属する。

• #P - NP問題の解を数える問題
• #P完全 - #P の中で最も難しい問題群
• AH - 算術的階層
• AP - 交替性チューリングマシンで多項式時間で解ける問題のクラス
• BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい）
• BQP - 量子コンピュータで多項式時間で解ける問題のクラス（解はおそらく正しい）
• Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス
• Co-NP完全 - Co-NP の中で最も難しい問題群
• DSPACE(f(n)) - 決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
• DTIME(f(n)) - 決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
• E - 線形な指数の指数関数時間で解ける問題のクラス（底を2とするDTIME(2^O(n))と等価）
• ESPACE - 線形な指数の指数関数領域で解ける問題のクラス
• EXPSPACE - 指数関数領域で解ける問題のクラス
• EXPTIME - 指数関数時間で解ける問題のクラス
• ELEMENTARY - 指数階層に属す問題のクラス（ループ深度が高々 2 のループプログラムで解ける問題のクラス）
• IP - 対話型証明系で多項式時間で解ける問題のクラス
• L - 対数領域で解ける問題のクラス
• LOGCFL - 文脈自由言語に還元可能な対数領域で解ける問題のクラス
• NC - 並列コンピュータ上で効率的に解ける問題のクラス（O((log n)^c）
• NEXPTIME - 非決定性機械で指数関数時間で解ける問題のクラス
• NL - 非決定性チューリングマシンで対数領域で解ける問題のクラス
• NP - 非決定性チューリングマシンで多項式時間で解ける問題のクラス（P≠NP予想も参照）。これはまた解に対して多項式長の witness が存在し、解の候補と witness が与えられたとき検証が決定性チューリングマシンで多項式時間で解ける問題のクラスに一致する
• NP完全 - NP の中で最も難しい問題のクラス
• NP困難 - NP完全かそれより難しい問題のクラス
• NSPACE(f(n)) - 非決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
• NTIME(f(n)) - 非決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
• P - 多項式時間で解ける問題のクラス
• P完全 - P の中で最も難しい問題のクラスであり、並列コンピュータで解ける
• PH - 多項式階層にあるクラス群の和集合
• PP - 確率的に多項式時間で解ける問題のクラス（解が正しい可能性は2分の1より若干大きい)
• PR - 原始再帰関数で解ける問題のクラス
• PSPACE - 多項式領域で解ける問題のクラス
• PSPACE完全 - PSPACE の中で最も難しい問題群
• R - 有限時間で解ける問題のクラス。つまり、チューリングマシンで解ける全問題の集合であり、帰納言語に相当
• RE - "YES" ならば停止し、"NO" ならば停止しないチューリングマシンの存在する問題のクラス。すなわち、帰納的可算言語に相当。これはまた解に対して witness が存在し、解の候補と witness が与えられたとき検証がチューリングマシンで解ける問題のクラスに一致する
• RP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解がNOの場合は正しくない可能性があるが、YESなら正しい）
• UP - 非決定性チューリングマシンで多項式時間で解ける決定問題のクラス（PとNPの中間）
• ZPP - 乱択アルゴリズムで解ける問題のクラス（解は常に正しいが、平均で多項式時間かかる）

参考文献

• Complexity Zoo - 500以上の複雑性クラスとその特性のリスト
• A diagram of the world of computability and complexity by Neil Immerman - 複雑性クラスの階層についての図
• Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP完全問題についての教科書的書籍