乱択アルゴリズム
最も基本的な確率的複雑性クラス。決定問題LがRPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率は1/2以上で、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率は1であるときに言う。(なお上述の「1/2」を0と1の間にある任意の定数に置き換えても定義は変わらない)。
乱数列の生成には、擬似乱数を使用することもあれば、真の乱数を利用することもある。「良い」乱数列である必要性に関しては、他の多くの乱数の応用の場合と同様だろう。再現性のためには、真の乱数であればどのような乱数列が使用されたかを全て保存しなければならない(擬似乱数であれば、シードだけ保存しておけば再現できる)。真の乱数には、それの生成に要する時間的コストといった問題もある(情報理論と物理法則にもとづく、絶対的な限界がある)。
決定問題LがBPPに属するとは、ある(最悪計算量の意味での)多項式時間乱択アルゴリズムAが存在して、A(x)が「はい」を出力した場合に x ∈ L {\displaystyle x\in {}L} である確率も、「いいえ」を出力した場合に x ∉ L {\displaystyle x\notin {}L} である確率も2/3以上であるときに言う。(なお上述の「2/3」を1/2と1の間にある任意の定数に置き換えても定義は変わらない)。