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. Such an algorithm is called a Las Vegas algorithm.

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.

The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.

Intersection definition

The class ZPP is exactly equal to the intersection of the classes RP 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 Las Vegas algorithm as follows:

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 expected 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:

By Markov's Inequality, the chance that it will yield an answer before we stop it is 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out".

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:

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 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 xX (for RP); of rejecting x when x is not in X is large but zero if xX (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.

Complexity-theoretic properties

It is known that ZPP is closed under complement; that is, ZPP = co-ZPP.

ZPP is low 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.

Connection to other classes

Since ZPP = RPcoRP, ZPP is obviously contained in both RP and coRP.

The class P 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.

A proof for ZPP = EXPTIME would imply that PZPP, as PEXPTIME (see time hierarchy theorem).

See also

External links

This article is issued from Wikipedia - version of the Sunday, January 17, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.