出典: フリー百科事典『ウィキペディア(Wikipedia)』
複雑性クラス (ふくざつせいクラス、英 : Complexity class )は、計算複雑性理論 において関連する複雑性 の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。
抽象機械 M によりO (f(n ))の計算資源 R を使って解く事が出来る問題の集合(n は入力長)
例えば、クラスNP は非決定性チューリングマシン で多項式時間 で解く事が出来る決定問題 の集合である。また、クラスPSPACE はチューリングマシン で多項式領域 で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題 の集合である(例えばFP )。
数理論理学 では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量 )。
ブラムの公理 を使うと、完全な計算模型 を参照しなくとも複雑性クラスを定義できる。
複雑性クラス間の関係
以下の表はいくつかの問題(または文法、言語)のクラスを計算複雑性理論の中で捉えて図示したものである。クラス X が Y の真部分集合 である場合、X を Y の下に置き、実線でそれらを接続している。X が部分集合であっても上位と等しい可能性もある場合、破線で接続している。決定可能か決定不能かは、どちらかと言えば計算可能性理論 の範疇であるが、ここでは複雑性クラスの関係を示すために入れてある。
複雑性クラス一覧
以下の一覧の各複雑性クラスには補問題 の集合である 'Co' の付くクラスが存在する。例えば、問題 L が NP に含まれるなら、その補問題は Co-NP に属する。
#P - NP問題の解を数える問題
#P完全 - #P の中で最も難しい問題群
AH - The arithmetic hierarchy
AP - 交替性チューリングマシン で多項式時間で解ける問題のクラス
BPP - 乱択アルゴリズム で多項式時間で解ける問題のクラス(解はおそらく正しい)
BQP - 量子コンピュータ で多項式時間で解ける問題のクラス(解はおそらく正しい)
Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス
Co-NP完全 - Co-NP の中で最も難しい問題群
DSPACE(f(n )) - 決定性機械で空間計算量 O(f(n )) で解ける問題のクラス
DTIME(f(n )) - 決定性機械で時間計算量 O(f(n )) で解ける問題のクラス
E - 線形な指数の指数関数時間で解ける問題のクラス
ESPACE - 線形な指数の指数関数領域で解ける問題のクラス
EXPSPACE - 指数関数領域で解ける問題のクラス
EXPTIME - 指数関数時間で解ける問題のクラス
IP - 対話型証明系 で多項式時間で解ける問題のクラス
L - 対数領域で解ける問題のクラス
LOGCFL - 文脈自由言語 に還元 可能な対数領域で解ける問題のクラス
NC - 並列コンピュータ上で効率的に解ける問題のクラス(O((log n )c )
NEXPTIME - 非決定性機械で指数関数時間で解ける問題のクラス
NL - 非決定性チューリングマシンで対数領域で解ける問題のクラス
NP - 非決定性チューリングマシンで多項式時間で解ける問題のクラス(P≠NP予想 も参照)
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"という解の場合には機械が停止しない可能性のある問題のクラス。すなわち、帰納的可算言語 に相当
RP - 乱択アルゴリズムで多項式時間で解ける問題のクラス(解がNOの場合は正しくない可能性があるが、YESなら正しい)
UP - 非決定性チューリングマシンで多項式時間で解ける決定問題のクラス(PとNPの中間)
ZPP - 乱択アルゴリズムで解ける問題のクラス(解は常に正しいが、平均で多項式時間かかる)
参考文献
[1]
Complexity Zoo - 400以上の複雑性クラスとその特性のリスト
Diagram 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完全問題についての教科書的書籍