ZPP (complexity)

In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer.

Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: The two definitions are equivalent.

This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial.

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: By Markov's Inequality, 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.

Definition: A verifier V for a set X is a Turing machine such that: 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.