ZPP

計算複雑性理論における ZPP とは、以下の属性をもつ確率的チューリング機械で解ける問題の複雑性クラスである。
なお ZPP とは "Zero-error Probabilistic Polynomial time" の略である。
換言すれば、ZPP に属する問題を解くアルゴリズムは完全に無作為なコインを投げるとも言える。常に正しい答えを返すので、ラスベガス法に分類される。入力長 "n" に関する多項式 "p"("n") があるとき、答えを得るまでにかかる時間の平均は "p"("n") 未満だが、最悪の場合はもっと長くなる。
あるいは、ZPP を以下の属性を持つ確率的チューリング機械で解ける問題のクラスと定義することもできる。
これら2つの定義は等価である。
ZPP の定義には確率的チューリング機械に基づいている。同様の複雑性クラスとして BPP や RP がある。クラス BQP は別のランダム性を持つ機械である量子コンピュータに基づいている。
積集合的定義.
クラス ZPP は、クラス RP と Co-RP の積集合に正確に対応している。これを ZPP の定義とすることも多い。RP と Co-RP の両方に属する問題は、次のようなラスベガス法による解法を持つ。
間違った答えを返すのは一方の機械だけであり、一回の繰り返しでその機械が間違う確率は50%であることに注意されたい。これはすなわち、"k"回繰り返すと "k" の指数関数的に間違う確率が減っていくことを意味し、結果として平均実行時間が多項式時間となる。これにより、RP と Co-RP の積集合が ZPP に含まれることを示される。
逆に ZPP が RP と Co-RP の積集合に含まれることを示すため、ZPPに属するある問題を解くラスベガス法 C を想定する。ここで次のような RP に属するアルゴリズムを構築できる。
証拠と証明.
クラス NP、RP、ZPP は、ある集合のメンバーシップの証明の手段と考えることもできる。
定義: 集合 X についての検査器 V は以下のようなチューリング機械であるとする。
文字列 w はメンバーシップの証明と考えることができる。証明が短い（入力長の多項式で表される長さ）なら、（V は多項式時間の決定性チューリング機械なので）効率的な検査が可能であり、その文字列 w を「証拠; witness」と呼ぶ。
注記:
クラス NP、RP、ZPP はメンバーシップの証拠を持つ集合である。NP はそのような証拠が存在しさえすればよい。これは非常に珍しい。2f(|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 であることも同時に明らかとなる（時間階層定理）。