ZPP (complexity)

<h2 id="intersection-definition">Intersection definition</h2>
The class ZPP is exactly equal to the intersection of the classes <a href="/facts/RP_(complexity)/KyYkqCHe">RP</a> and co-RP. This is often taken to be the definition of ZPP. To show this, first note that every problem which is in both RP and co-RP has a <a href="/facts/Las_Vegas_algorithm/K43MRwQz">Las Vegas algorithm</a> as follows:

<ul><li>Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B.</li>
<li>Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step.</li></ul>
Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the <a href="/facts/Expected_value/1XV0JKL8">expected</a> running time is polynomial. This shows that RP intersect co-RP is contained in ZPP.
To show that ZPP is contained in RP intersect co-RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:

<ul><li>Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.</li></ul>
By <a href="/facts/Markov%2527s_inequality/Re85kMQJ">Markov's Inequality</a>, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out".

<h2 id="witness-and-proof">Witness and proof</h2>
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:

<ul><li>if x is in X then there exists a string w such that V(x,w) accepts;</li>
<li>if x is not in X, then for all strings w, V(x,w) rejects.</li></ul>
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:

<ul><li>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.</li>
<li>For all x in X there must be a witness to its membership in X.</li>
<li>The witness need not be a traditionally construed proof. If V is a probabilistic Turing machine which could possibly accept x if x is in X, then the proof is the string of coin flips which leads the machine to accept x (provided all members in X have some witness and the machine never accepts a non-member).</li>
<li>The co-concept is a proof of non-membership, or membership in the complement set.</li></ul>
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 probabilistic 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 ∉ X (for RP); of rejecting x when x is not in X is large but zero if x ∈ 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.

<h2 id="complexity-theoretic-properties">Complexity-theoretic properties</h2>
ZPP is closed under complement, i.e., ZPP = co-ZPP (this follows from ZPP = RP ∩ co-RP). 
ZPP is <a href="/facts/Low_(complexity)/xxd0DptC">low</a> for itself, meaning that a ZPP machine with the power to solve ZPP problems instantly (a ZPP oracle machine) is not any more powerful than the machine without this extra power. In symbols, ZPPZPP = ZPP.
ZPPNPBPP = ZPPNP.
NPBPP is contained in ZPPNP.

<h2 id="connection-to-other-classes">Connection to other classes</h2>
Since ZPP = RP ∩ coRP, ZPP is obviously contained in both RP and coRP.
The class <a href="/facts/P_(complexity)/2TYvck4k">P</a> is contained in ZPP, and some computer scientists have conjectured that P = ZPP, i.e., every Las Vegas algorithm has a deterministic polynomial-time equivalent.
There exists an oracle relative to which ZPP = <a href="/facts/EXPTIME/GbTmY8t5">EXPTIME</a>. A proof for ZPP = <a href="/facts/EXPTIME/GbTmY8t5">EXPTIME</a> would imply that P ≠ ZPP, as P ≠ EXPTIME (see <a href="/facts/Time_hierarchy_theorem/sm75DR1s">time hierarchy theorem</a>).

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/BPP_(complexity)/6woy25bz">BPP</a></li>
<li><a href="/facts/RP_(complexity)/KyYkqCHe">RP</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a>: <a href="https://complexityzoo.net/Complexity_Zoo:Z#zpp">ZPP Class ZPP</a></li></ul>

ZPP (complexity) open-in-new

ZPP (complexity)