複雑性クラス
Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス
Co-NP完全 - Co-NP の中で最も難しい問題群
DSPACE(f(n)) - 決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
DTIME(f(n)) - 決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
E - 線形な指数の指数関数時間で解ける問題のクラス（底を2とするDTIME(2O(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 - 乱択アルゴリズムで解ける問題のクラス（解は常に正しいが、平均で多項式時間かかる）
脚注[脚注の使い方]^ Optimal Reliability Modeling: Principles and Applications Kuo, Way; Zuo, Ming J. (2003), John Wiley & Sons, p. 62
参考文献
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完全問題についての教科書的書籍
表
話
編
歴
主な複雑性クラス
実用的な時間で解けるクラス
DLOGTIME
AC0
ACC0
TC0
L
SL
RL
NL
NC
SC
CC
P
P完全
ZPP
RP
BPP
BQP
APX
実用的な時間で解けないと疑われているクラス
UP
NP
NP完全
NP困難
co-NP
co-NP完全
AM
QMA
PH
?P
PP
#P
#P完全
IP
PSPACE
実用的な時間では解けないクラス
EXPTIME
NEXPTIME
EXPSPACE
ELEMENTARY
PR
R
RE
ALL
クラス階層
多項式階層
指数階層
グジェゴルチク階層
算術的階層
ブーリアン階層
クラスの族
DTIME
NTIME
DSPACE
NSPACE
PCP
対話型証明系
一覧・ カテゴリ
記事の検索おまかせリスト▼オプションを表示暇つぶしWikipedia
Size:18 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef
