複雑性クラス一覧
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/28 02:38 UTC 版)
以下の一覧の各複雑性クラスには補問題の集合である '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 - 線形な指数の指数関数時間で解ける問題のクラス 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 - 乱択アルゴリズムで解ける問題のクラス（解は常に正しいが、平均で多項式時間かかる）
※この「複雑性クラス一覧」の解説は、「複雑性クラス」の解説の一部です。
「複雑性クラス一覧」を含む「複雑性クラス」の記事については、「複雑性クラス」の概要を参照ください。
- 複雑性クラス一覧のページへのリンク
