|
計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。 * YES または NO の常に正しい解を返す。 * 実行時間に制限はないが、任意の入力長について平均で多項式時間かかる。 なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。 換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 ''n'' に関する多項式 ''p''(''n'') があるとき、答えを得るまでにかかる時間の平均は ''p''(''n'') 未満だが、最悪の場合はもっと長くなる。 あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。 * 常に多項式時間である。 * 解として YES、NO、DO NOT KNOW の三種類を返す。 * 解は DO NOT KNOW でない場合は常に正しい。 * 正解が YES である場合、YES を返す確率は最低でも 1/2 である。 * 正解が NO である場合、NO を返す確率は最低でも 1/2 である。 これら2つの定義は等価である。 ZPP の定義には確率的チューリング機械に基づいている。同様の複雑性クラスとして BPP や RP がある。クラス BQP は別のランダム性を持つ機械である量子コンピュータに基づいている。 == 積集合的定義 == クラス 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 を返すという方式で実現される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ZPP」の詳細全文を読む スポンサード リンク
|