ZPP (complexity) - Witness and Proof

Witness and Proof

The classes NP, RP and ZPP can be thought of in terms of proof of membership in a set.

Definition: A verifier V for a set X is a Turing machine such that:

• if x is in X then there exists a string w such that V(x,w) accepts;
• if x is not in X, then for all strings w, V(x,w) rejects.

The string w can be thought of as the proof of membership. In the case of short proofs (of length bounded by a polynomial in the size of the input) which can be efficiently verified (V is a polynomial-time deterministic Turing machine), the string w is called a witness.

Notes:

• The definition is very asymmetric. The proof of x being in X is a single string. The proof of x not being in X is the collection of all strings, none of which is a proof of membership.
• The availability of witness is uniform. For all x in X there must be a witness. It is not the case where certain x in X are too difficult to verify, whereas most are not.
• The witness needn't be a traditionally construed proof. If V is a probabilisitic Turing Machine which could possible accept x if x is in X, then the proof is the string of coin flips which leads the machine, by luck, intuition, or genius, to accepting x.
• The co- concept is a proof of non-membership, or membership in the complement set.

The classes NP, RP and ZPP are sets which have witnesses for membership. The class NP requires only that witnesses exist. They may be very rare. Of the 2f(|x|) possible strings, with f a polynomial, only one need cause the verifier to accept (if x is in X. If x is not in X, no string will cause the verifier to accept).

For the classes RP and ZPP any string chosen at random will likely be a witness.

The corresponding co-classes have witness for non-membership. In particular, co-RP is the class of sets for which, if x is not in X, any randomly chosen string is likely to be a witness for non-membership. ZPP is the class of sets for which any random string is likely to be a witness of x in X, or x not in X, which ever the case may be.

Connecting this definition with other definitions of RP, co-RP and ZPP is easy. The probablisitic polynomial-time Turing Machine V*_w(x) corresponds to the deterministic polynomial-time Turing Machine V(x,w) by replacing the random tape of V* with a second input tape for V on which is written the sequence of coin flips. By selecting the witness as a random string, the verifier is a probabilistic polynomial-time Turing Machine whose probability of accepting x when x is in X is large (greater than 1/2, say), but zero if x is not in X (for RP); of rejecting x when x is not in X is large but zero if x is in X (for co-RP); and of correctly accepting or rejecting x as a member of X is large, but zero of incorrectly accepting or rejecting x (for ZPP).

By repeated random selection of a possible witness, the large probability that a random string is a witness gives an expected polynomial time algorithm for accepting or rejecting an input. Conversely, if the Turing Machine is expected polynomial-time (for any given x), then a considerable fraction of the runs must be polynomial-time bounded, and the coin sequence used in such a run will be a witness.

ZPP should be contrasted with BPP. The class BPP does not require witnesses, although witnesses are sufficient (hence BPP contains RP, co-RP and ZPP). A BPP language has V(x,w) accept on a (clear) majority of strings w if x is in X, and conversely reject on a (clear) majority of strings w if x is not in X. No single string w need be definitive, and therefore they cannot in general be considered proofs or witnesses.