ZPP
証拠選択を乱数列とすることで検査器は確率的チューリング機械となり、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 が必要とはされない。従って、一般に証明とも証拠とも見なされない。