Editing ZPP (complexity) (section)

{{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]].