複雑性クラスのリスト
これは計算複雑性理論における計算複雑性クラスのリストです。その他の計算と計算複雑性に関する主題については、計算可能性と計算複雑性に関するトピックのリストを参照してください。
これらのクラスの多くは、元のクラスに含まれるすべての言語の補語から構成される「共」のパートナーを持ちます。例えば、言語LがNPに属する場合、Lの補語はco-NPに属します。（これはNPの補語がco-NPであることを意味するわけではありません。NPとNPの両方に属することが知られている言語もあれば、どちらにも属さないことが知られている言語もあります。）
あるクラスの「最も難しい問題」とは、そのクラスの他のすべての問題がそのクラスに還元できるような、そのクラスに属する問題を指します。
| #P | NP問題の解を数える |
| #P完全 | #Pにおける最も難しい問題 |
| 2-EXPTIME | 二重指数時間で解ける |
| AC 0 | 深さが制限された回路複雑度クラス |
| ACC 0 | 深さが制限され、ゲート数が計数される回路複雑度クラス |
| AC | 回路計算量クラス |
| AH | 算術階層 |
| AP | 交代型チューリングマシンが多項式時間で解ける問題のクラス。 [1] |
| APX | 近似比が一定である近似アルゴリズムを持つ最適化問題[1] |
| 午前 | アーサー・マーリン・プロトコル[1]により多項式時間で解ける |
| BPP | ランダム化アルゴリズムによって多項式時間で解ける（答えはおそらく正しい） |
| BPL | 両側誤差を持つ確率チューリングマシンを用いて対数空間と多項式時間で解ける問題 |
| BQP | 量子コンピュータで多項式時間で解ける（おそらく正解） |
| 共同NP | 「いいえ」の答えは非決定性機械によって多項式時間で確認可能 |
| 共NP完全 | 共NPにおける最も難しい問題 |
| DLIN | 決定性マルチテープチューリングマシンによってO ( n ) 時間で解ける |
| DSPACE( f ( n )) | 空間O ( f ( n ) )を持つ決定論的マシンによって解ける。 |
| DTIME( f ( n )) | 決定論的マシンによってO ( f ( n ))の時間で解ける。 |
| E | 線形指数で指数時間で解ける |
| 初等 | 指数階層におけるクラスの和集合 |
| 空間 | 線形指数を持つ指数空間で解ける |
| 指数 | EXPTIMEと同じ |
| 指数空間 | 指数空間で解ける |
| 指数時間 | 指数時間で解ける |
| FNP | 関数問題におけるNPの類似 |
| FP | 関数問題におけるPの類似 |
| FP NP | 関数問題におけるP NPの類似物。巡回セールスマン問題の発祥地 |
| FPT | 固定パラメータで扱いやすい |
| GapL | 行列の整数行列式の計算に対数空間還元可能 |
| IP | 対話型証明システムによって多項式時間で解ける |
| L | 対数空間（小さい）で解ける |
| LOGCFL | 文脈自由言語に対数空間還元可能 |
| MA | マーリン・アーサー・プロトコルにより多項式時間で解ける |
| NC | 並列コンピュータ上で効率的に（多重対数時間で）解ける |
| NE | 非決定性機械によって線形指数を持つ指数時間で解ける |
| NESPACE | 線形指数を持つ指数空間を持つ非決定性機械によって解ける |
| NEXP | NEXPTIMEと同じ |
| ネクススペース | 指数空間を持つ非決定性マシンで解ける |
| ネクスタイム | 非決定性機械によって指数時間で解ける |
| NL | 「はい」の回答は対数スペースでチェック可能 |
| NLIN | 非決定性マルチテープチューリングマシンによってO ( n ) 時間で解ける |
| 非初等的 | 基本の補数 |
| NP | 「はい」の回答は多項式時間で確認可能（複雑性クラスPおよびNPを参照） |
| NP完全 | NPにおける最も難しい、または最も表現力豊かな問題 |
| NP容易 | 関数問題におけるP NPの類似。FP NPの別名。 |
| NP同等 | FP NPにおける最も難しい問題 |
| NP困難 | NPのすべての問題と同じくらい難しいが、同じ複雑さのクラスにあるとは知られていない |
| NSPACE( f ( n )) | 空間O ( f ( n ))の非決定性マシンで解ける。 |
| NTIME( f ( n )) | 非決定性マシンによってO ( f ( n ))の時間で解ける。 |
| P | 多項式時間で解ける |
| P完全 | 並列コンピュータで解くのが最も難しいPの問題 |
| P/多項式 | 入力サイズのみに依存する「アドバイス文字列」が与えられた場合、多項式時間で解ける |
| PCP | 確率的に検証可能な証明 |
| PH | 多項式階層におけるクラスの和集合 |
| PL | 対数空間ランダム化マシンを用いて、確率1 ⁄ 2以上の多項式時間で解ける |
| P NP | NPの問題は、オラクルを用いて多項式時間で解ける。Δ 2 P とも呼ばれる |
| PP | 確率多項式（正解確率は1/2よりわずかに高い） |
| PPAD | 有向グラフ上の多項式パリティ論証 |
| PR | 算術関数を再帰的に構築することで解ける |
| PSPACE | 多項式空間で解ける。 |
| PSPACE完全 | PSPACEにおける最も難しい問題 |
| PTAS | 多項式時間近似スキーム（APXのサブクラス） |
| QIP | 量子インタラクティブ証明システムにより多項式時間で解決可能。 |
| QMA | NPの量子アナログ |
| R | 有限時間で解ける |
| 再 | 限られた時間内に「はい」と答えられる問題はありますが、「いいえ」と答えることは決してないかもしれません |
| RL | ランダムアルゴリズムによって対数空間で解ける（「いいえ」はおそらく正解、「はい」は間違いなく正解） |
| RP | ランダムアルゴリズムによって多項式時間で解ける（「いいえ」はおそらく正解、「はい」は間違いなく正解） |
| SL | 対数空間の問題は、無向グラフの与えられた頂点間にパスが存在するかどうかを判断することに帰着します。2004年10月、このクラスは実際にはLに等しいことが発見されました |
| S 2 P | 多項式時間で決定論的に判定される同時進行の1ラウンドゲーム[2] |
| TFNP | 非決定性多項式時間で解ける全関数問題。このクラスの問題は、すべての入力にその妥当性を効率的に検証できる出力があるという性質があり、計算上の課題は有効な出力を見つけることです |
| 上 | 明確な非決定性多時間関数。 |
| ZPL | ランダムアルゴリズムで解ける（答えは常に正しく、平均空間使用量は対数的） |
| ZPP | ランダムアルゴリズムで解ける（答えは常に正しく、平均実行時間は多項式） |
参考文献
- ^ abc サンジーヴ・アローラ、ボアズ・バラク（2009年）、計算複雑性：現代的アプローチ、ケンブリッジ大学出版局、第1版、ISBN 978-0-521-42426-4
- ^ 「S2P：対称階層の第2レベル」スタンフォード大学複雑性動物園。2012年10月14日時点のオリジナルよりアーカイブ。 2011年10月27日閲覧
外部リンク
- Complexity Zoo - 500 以上の複雑性クラスとその特性のリスト
