BPP (計算複雑性理論)

計算複雑性理論において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 $\subseteq$ BPP $\subseteq$ PH は証明されている。 しかし NP$\subseteq$BPP なのか、BPP$\subseteq$NP なのか、あるいは BPP = NP なのかは不明である。

なおこのクラスとよく似た誤り確率が高々1/2 のクラス（クラスPP）は NP を含むことが証明されている。

確率的チューリングマシンを少し拡張すると、量子チューリングマシンができるのと同じように、BPPの量子コンピュータに対応する計算量のクラスとしてBQPが存在する。

関連するクラス

• クラスPP - クラス BPPとほとんど同じ概念のクラスだがこちらは誤り確率が高々1/2である。当然ながら BPP　$\subseteq$ PP である。
• クラスRP - YES であるときの誤り確率は高々1/2 であり、NO のときは絶対に間違えないクラス。

関連項目

• 乱択アルゴリズム
• モンテカルロ法 / ラスベガス法