BPP (計算複雑性理論)

BPPは、補問題について閉じていることが知られている。つまり、BPP=co-BPPである。 このクラスは特に NP との位置が不定のクラスである。 P ${\displaystyle \subseteq }$ BPP ${\displaystyle \subseteq }$ PH は証明されている。 しかし NP${\displaystyle \subseteq }$BPP なのか、BPP${\displaystyle \subseteq }$NP なのか、あるいは BPP = NP なのかは不明である。

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

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

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

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