BPP (計算複雑性理論)
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
計算複雑性理論において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 BPP PH は証明されている。 しかし NP BPP なのか、BPP NP なのか、あるいは BPP = NP なのかは不明である。
なおこのクラスとよく似た誤り確率が高々1/2 のクラス（クラスPP）は NP を含むことが証明されている。
確率的チューリングマシンを少し拡張すると、量子チューリングマシンができるのと同じように、BPPの量子コンピュータに対応する計算量のクラスとしてBQPが存在する。