積集合的定義

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

積集合的定義

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 03:55 UTC 版)

「ZPP」の記事における「積集合的定義」の解説

クラス ZPP は、クラス RP と Co-RP の積集合に正確に対応している。これを ZPP の定義とすることも多い。RP と Co-RP の両方に属する問題は、次のようなラスベガス法による解法を持つ。 RP に属するアルゴリズム A と（おそらく全く異なる）Co-RP に属するアルゴリズム B があり、両者がある言語 L を認識するとする。 L に属する入力を A に与えた場合、YES を返すなら、その解は正しい。L に属さない入力を B に与えた場合、NO を返すなら、その解は正しい。どちらも正解を返さない場合、このステップを再度繰り返す。 間違った答えを返すのは一方の機械だけであり、一回の繰り返しでその機械が間違う確率は50%であることに注意されたい。これはすなわち、k回繰り返すと k の指数関数的に間違う確率が減っていくことを意味し、結果として平均実行時間が多項式時間となる。これにより、RP と Co-RP の積集合が ZPP に含まれることを示される。 逆に ZPP が RP と Co-RP の積集合に含まれることを示すため、ZPPに属するある問題を解くラスベガス法 C を想定する。ここで次のような RP に属するアルゴリズムを構築できる。 C を平均実行時間の2倍まで実行する。もし解が得られたら、それが解となる。停止させるまでに解が得られない場合、NO を解とする。マルコフの不等式によれば、停止させる前に解が得られる確率は 1/2 である。従って、実際には YES であるはずなのに停止させて NO を返す確率は 1/2 であり、これは RP に属する問題を解くアルゴリズムの定義に一致する。Co-RP についても同様に、C が時間内に解を返さない場合に YES を返すという方式で実現される。