ZPP
クラス ZPP は、クラス RP と Co-RP の積集合に正確に対応している。これを ZPP の定義とすることも多い。RP と Co-RP の両方に属する問題は、次のようなラスベガス法による解法を持つ。
RP に属するアルゴリズム A と(おそらく全く異なる)Co-RP に属するアルゴリズム B があり、両者がある言語 L を認識するとする。
L に属する入力を A に与えた場合、YES を返すなら、その解は正しい。L に属さない入力を B に与えた場合、NO を返すなら、その解は正しい。どちらも正解を返さない場合、このステップを再度繰り返す。
間違った答えを返すのは一方の機械だけであり、一回の繰り返しでその機械が間違う確率は50%であることに注意されたい。これはすなわち、k回繰り返すと k の指数関数的に間違う確率が減っていくことを意味し、結果として平均実行時間が多項式時間となる。