ZPP

計算複雑性理論における 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 を返すという方式で実現される。

証拠と証明

クラス NP、RP、ZPP は、ある集合のメンバーシップの証明の手段と考えることもできる。

定義: 集合 X についての検査器 V は以下のようなチューリング機械であるとする。

• x が X に含まれる場合、ある文字列 w が存在し V(x,w) は受理される。
• x が X に含まれない場合、あらゆる文字列 w について V(x,w) は受理されない。

文字列 w はメンバーシップの証明と考えることができる。証明が短い（入力長の多項式で表される長さ）なら、（V は多項式時間の決定性チューリング機械なので）効率的な検査が可能であり、その文字列 w を「証拠; witness」と呼ぶ。

注記:

• この定義は非対称である。x が X に含まれることの証明には1つの文字列があればよい。x が X に含まれないことの証明には、メンバーシップの証明ではない全文字列の集合が必要となる。
• 証拠の入手可能性は一様である。X に含まれる全ての x には必ず証拠が対応している。特定の x について検証が難しく、他はそうでないという話ではない。
• 証拠はいわゆる古典的な意味での証明である必要はない。V が X に属する x を受理する確率的チューリング機械だった場合、証明はコイントスのような文字列であり、運がよければ x を受理することになる。
• その補概念は、非メンバーシップの証明か、補集合のメンバーシップの証明となる。

クラス NP、RP、ZPP はメンバーシップの証拠を持つ集合である。NP はそのような証拠が存在しさえすればよい。これは非常に珍しい。2^f(|x|) 個の文字列のうち（f()は多項式）、1つの文字列だけが検査器に受理される（x が X に含まれる場合。そうでない場合、どの文字列も受理されない）。

クラス RP と ZPP では無作為に選んだ文字列が証拠となりうる。

対応する補問題のクラスは非メンバーシップの証拠を持つ。特に Co-RP は、x が X に含まれない場合、無作為に選んだ文字列が非メンバーシップの証拠となりうる集合のクラスである。ZPP は無作為に選んだ文字列がメンバーシップの証拠にも非メンバーシップの証拠にもなりうる集合のクラスである。

この定義と RP、Co-RP、ZPP の通常の定義を結びつけるのは容易である。確率的多項式時間チューリング機械 V^*_w(x) を決定性多項式時間チューリング機械 V(x,w) と対応させるには、V^* の乱数テープを V の第二のテープにコイントスの列を書き込んだものと置き換えればよい。証拠選択を乱数列とすることで検査器は確率的チューリング機械となり、x が X に含まれるときにそれを受理する確率は大きく（1/2以上）、X に含まれないときに受理する確率はゼロとなる（RPの場合）。あるいは、x が X に含まれないとき受理しない確率は大きく、X に含まれるときに受理しない確率はゼロとなる（Co-RPの場合）。あるいはまた、受理・不受理を正しく行う確率は大きく、不正に受理・不受理する確率はゼロとなる（ZPPの場合）。

可能な証拠を無作為選択することを繰り返すと、大きな確率で無作為文字列が証拠となって受理・不受理を決定する多項式時間アルゴリズムになる。逆にチューリング機械が多項式時間で完了するなら、その処理の大部分は多項式時間内に制限され、そこで使われたコイントスの列は証拠となる。

ZPP は BPP と対比させられる。BPP は証拠を必要としないが、証拠があれば十分である（従って、BPP は RP も Co-RP も ZPP も包含する）。BPP言語の V(x,w) は x が X に含まれるなら大部分の文字列 w で受理され、x が X に含まれないなら大部分の文字列 w で不受理となる。特定の文字列 w が必要とはされない。従って、一般に証明とも証拠とも見なされない。

他のクラスとの関係

ZPP=RP ∩ Co-RP であるから、ZPP は明らかに RP と Co-RP に含まれる。

クラス P は ZPP に含まれる。これについて P=ZPP と予想する者もいる。すなわち、ラスベガス法には多項式時間の決定的アルゴリズムが必ず対応して存在するという考え方である。

ZPP = EXPTIME かどうかは未だ明らかになっていない（一般に違うと予想されている）。P=ZPP であることが明らかになれば、ZPP ≠ EXPTIME であることも同時に明らかとなる（時間階層定理）。

外部リンク

• ZPP - from Complexity Zoo