ラスベガス法
平均実行時間が多項式時間となるラスベガス法をもつ決定問題の複雑性クラスを ZPP と呼ぶ。
次のような性質がある。
Z P P = R P ∩ co- R P . {\displaystyle \mathbf {ZPP} =\mathbf {RP} \cap {\text{co-}}\mathbf {RP} .}
これは、ラスベガス法に属するアルゴリズムを構築する方法と密接に関係している。RPクラスは、多項式時間の乱択アルゴリズムがある決定問題のクラスであり、解が「no」であるときは常に正しいが、解が「yes」であるときは間違っている可能性がある。そのようなアルゴリズムが、ある問題とその補問題(「yes」と「no」が逆転した問題)について存在するとき、その2つのアルゴリズムを同時にかつ繰り返し実行するとする。すると、最終的にどちらかで間違いのない解が得られる。これが多項式時間を期待できるラスベガス法のアルゴリズムを構築する標準的な方法である。ラスベガス法には最悪実行時間の上限が存在しないことに注意されたい。