ZPP
その補概念は、非メンバーシップの証明か、補集合のメンバーシップの証明となる。
クラス NP、RP、ZPP はメンバーシップの証拠を持つ集合である。NP はそのような証拠が存在しさえすればよい。これは非常に珍しい。2 個の文字列のうち(f()は多項式)、1つの文字列だけが検査器に受理される(x が X に含まれる場合。そうでない場合、どの文字列も受理されない)。
クラス RP と ZPP では無作為に選んだ文字列が証拠となりうる。
対応する補問題のクラスは非メンバーシップの証拠を持つ。特に Co-RP は、x が X に含まれない場合、無作為に選んだ文字列が非メンバーシップの証拠となりうる集合のクラスである。ZPP は無作為に選んだ文字列がメンバーシップの証拠にも非メンバーシップの証拠にもなりうる集合のクラスである。
この定義と RP、Co-RP、ZPP の通常の定義を結びつけるのは容易である。確率的多項式時間チューリング機械 Vw(x) を決定性多項式時間チューリング機械 V(x,w) と対応させるには、V の乱数テープを V の第二のテープにコイントスの列を書き込んだものと置き換えればよい。