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が存在する。