BPP_(計算複雑性理論)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > BPP_(計算複雑性理論)の意味・解説 

BPP (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/16 23:27 UTC 版)

計算複雑性理論においてBPPとは、確率的チューリング機械によって、誤り確率が高々1/3で多項式時間で解ける決定問題複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。

定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。

他の計算量クラスとの関係

BPPは、補問題について閉じていることが知られている。つまり、BPP=co-BPPである。 このクラスは特に NP との位置が不定のクラスである。 P 一覧・ カテゴリ




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「BPP_(計算複雑性理論)」の関連用語




4
98% |||||







BPP_(計算複雑性理論)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



BPP_(計算複雑性理論)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのBPP (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS