Editing ZPP (complexity)

{{Short description|Concept in computer science}}
{{no footnotes|date=January 2013}}
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|ZPP in relation to other probabilistic complexity classes ([[RP (complexity)|RP]], co-RP, [[BPP (complexity)|BPP]], [[BQP]], [[PP (complexity)|PP]]), which generalise [[P (complexity)|P]] within [[PSPACE]]. It is unknown if any of these containments are strict.]]
In [[computational complexity theory|complexity theory]], '''ZPP''' (zero-error probabilistic [[polynomial time]]) is the [[complexity class]] of problems for which a [[probabilistic Turing machine]] exists with these properties:

* It always returns the correct YES or NO answer.
* The running time is polynomial in expectation for every input.

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:
* It always runs in polynomial time.
* It returns an answer YES, NO or DO NOT KNOW.
* The answer is always either DO NOT KNOW or the correct answer.
* It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise).
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 '''[[Bounded-error probabilistic polynomial|BPP]]''' and '''[[RP (complexity)|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 (complexity)|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:

* Suppose we have a language L recognized by both the '''RP''' algorithm A and the (possibly completely different) '''co-RP''' algorithm B.
* 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.

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 ''k''th round shrinks exponentially in ''k'', showing that the [[expected value|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:
* 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.
By [[Markov's inequality|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. 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:
* 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. 
* For all x in X there must be a witness to its membership in X. 
* 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).
* 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 2<sup>''f''(|''x''|)</sup> 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*<sub>w</sub>''(''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.

== Complexity-theoretic properties ==

'''ZPP''' is closed under complement, i.e., '''ZPP''' = co-'''ZPP''' (this follows from '''ZPP''' = '''RP''' ∩ co-'''RP'''). 

ZPP is [[low (complexity)|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, '''ZPP'''<sup>'''ZPP'''</sup> = '''ZPP'''.

'''ZPP'''<sup>'''NP'''<sup>'''BPP'''</sup></sup> = '''ZPP'''<sup>'''NP'''</sup>.

'''NP'''<sup>'''BPP'''</sup> is contained in '''ZPP'''<sup>'''NP'''</sup>.

== Connection to other classes ==
Since '''ZPP''' = '''RP''' ∩ '''coRP''', '''ZPP''' is obviously contained in both '''RP''' and '''coRP'''.

The class '''[[P (complexity)|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.

There exists an oracle relative to which '''ZPP''' = '''[[EXPTIME]]'''. A proof for '''ZPP''' = '''[[EXPTIME]]''' would imply that '''P''' ≠ '''ZPP''', as '''P''' ≠ '''EXPTIME''' (see [[time hierarchy theorem]]).

== See also ==
* '''[[BPP (complexity)|BPP]]'''
* '''[[RP (complexity)|RP]]'''

==External links==
*{{CZoo|Class ZPP|Z#zpp ZPP}}

{{ComplexityClasses}}

[[Category:Probabilistic complexity classes]]