関連するクラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:37 UTC 版)
「P (計算複雑性理論)」の記事における「関連するクラス」の解説
クラス NP - 提出された答えの検算がクラス P になる決定問題のクラス。 クラス FP - クラス P と類似した概念ではあるが、クラス P とは違い解を出力することができる問題のクラス。 クラス RP - 答えが no のときは必ず no で返すが、答えが yes のときはある確率で no と答えることがある乱択算法によって解かれる判定問題のクラス。モンテカルロ法などの手法を計算理論上で解析するために生まれた。 多項式階層 表 話 編 歴 主な複雑性クラス(一覧)Considered feasible DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC PP完全 ZPP RP BPP BQP APX Suspected infeasible UP NPNP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P#P完全 IP PSPACE Considered infeasible EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL クラス階層 多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層 クラスの族 DTIME NTIME DSPACE NSPACE PCP 対話型証明系
※この「関連するクラス」の解説は、「P (計算複雑性理論)」の解説の一部です。
「関連するクラス」を含む「P (計算複雑性理論)」の記事については、「P (計算複雑性理論)」の概要を参照ください。
関連するクラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 02:46 UTC 版)
「BPP (計算複雑性理論)」の記事における「関連するクラス」の解説
クラスPP - クラス BPPとほとんど同じ概念のクラスだがこちらは誤り確率が高々1/2である。当然ながら BPP ⊆ {\displaystyle \subseteq } PP である。 クラスRP - YES であるときの誤り確率は高々1/2 であり、NO のときは絶対に間違えないクラス。
※この「関連するクラス」の解説は、「BPP (計算複雑性理論)」の解説の一部です。
「関連するクラス」を含む「BPP (計算複雑性理論)」の記事については、「BPP (計算複雑性理論)」の概要を参照ください。
Weblioに収録されているすべての辞書から関連するクラスを検索する場合は、下記のリンクをクリックしてください。
全ての辞書から関連するクラス
を検索
- 関連するクラスのページへのリンク
