複雑性クラス - Wikipedia複雑性クラス一覧[編集] 以下の一覧の各複雑性クラスには補問題の集合である '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)) - 決定
