PP (計算複雑性理論)
BPP は PP のサブセットであり、より効率的な乱択アルゴリズムのあるサブセットと言える。その違いは間違う確率であり、BPP は 1/2 以上のある固定の定数 c で示される確率(2/3 とか 501/1000)で正しい解を返さなければならない。この場合、アルゴリズムを繰り返し実行することでチェルノフ限界を使って 1 未満の任意の確率で多数決的に正しい解を得ることができる。c が 1/2 に近いほど繰り返し回数を多くする必要があるが、繰り返し回数は n には依存しない。
重要な点として、定数 c が入力長に依存してはならない。一方、PP アルゴリズムでは以下のようなものが許される。
YES が正解の場合、YES を確率 1/2+1/2 で返す。このとき n は入力長である。
NO が正解の場合、YES を確率 1/2 で返す。
これらの確率は非常に近いので(特に n が大きい場合)、何回も繰り返したとしても正解を高い確率で示すのは難しい。多数決方式とチェルノフ限界で、ある確率で正解を示すには、n の指数関数回の繰り返しが必要となる。これは、微妙に細工を施したイカサマのコインを何度も投げて、どちらの面が出やすいかを明らかにするのと似ている。