PP vs BPP

ウィキペディア小見出し辞書

PP vs BPP

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/27 03:33 UTC 版)

「PP (計算複雑性理論)」の記事における「PP vs BPP」の解説

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