ZPP
クラス 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 を受理することになる。
ZPP=RP ∩ Co-RP であるから、ZPP は明らかに RP と Co-RP に含まれる。
クラス P は ZPP に含まれる。これについて P=ZPP と予想する者もいる。すなわち、ラスベガス法には多項式時間の決定的アルゴリズムが必ず対応して存在するという考え方である。
ZPP = EXPTIME かどうかは未だ明らかになっていない(一般に違うと予想されている)。P=ZPP であることが明らかになれば、ZPP ≠ EXPTIME であることも同時に明らかとなる(時間階層定理)。