複雑性クラス
ELEMENTARY - 指数階層に属す問題のクラス(ループ深度が高々 2 のループプログラムで解ける問題のクラス)
IP - 対話型証明系で多項式時間で解ける問題のクラス
L - 対数領域で解ける問題のクラス
LOGCFL - 文脈自由言語に還元可能な対数領域で解ける問題のクラス
NC - 並列コンピュータ上で効率的に解ける問題のクラス(O((log n))
NEXPTIME - 非決定性機械で指数関数時間で解ける問題のクラス
NL - 非決定性チューリングマシンで対数領域で解ける問題のクラス
NP - 非決定性チューリングマシンで多項式時間で解ける問題のクラス(P≠NP予想も参照)。これはまた解に対して多項式長の witness が存在し、解の候補と witness が与えられたとき検証が決定性チューリングマシンで多項式時間で解ける問題のクラスに一致する
NP完全 - NP の中で最も難しい問題のクラス
NP困難 - NP完全かそれより難しい問題のクラス
NSPACE(f(n)) - 非決定性機械で空間計算量 O(f(n)) で解ける問題のクラス
NTIME(f(n)) - 非決定性機械で時間計算量 O(f(n)) で解ける問題のクラス
以下の一覧の各複雑性クラスには補問題の集合である '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)と等価)
ESPACE - 線形な指数の指数関数領域で解ける問題のクラス
EXPSPACE - 指数関数領域で解ける問題のクラス
EXPTIME - 指数関数時間で解ける問題のクラス