これら2つの定義は等価である。定義には確率的チューリング機械に基づいている。別のランダム性を持つ機械である量子コンピュータに基づいている。積集合に正確に対応している。定義とすることも多い。両方に属する問題は、次のようなラスベガス法による解法を持つ。返すなら、その解は正しい。返すなら、その解は正しい。どちらも正解を返さない場合、このステップを再度繰り返す。間違った答えを返すのは一方の機械だけであり、一回の繰り返しでその機械が間違う確率は50%であることに注意されたい。指数関数的に間違う確率が減っていくことを意味し、結果として平均実行時間が多項式時間となる。含まれることを示される。属するアルゴリズムを構築できる。平均実行時間の2倍まで実行する。解が得られたら、それが解となる。