# ZPP

In

complexity theory,

**ZPP** (Zero-error Probabilistic Polynomial time) is the set 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 random, but on average is polynomial

In other words, the algorithm is allowed to flip a truly-random coin while it's running. It always returns the correct answer. 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.

The class ZPP is exactly equal to the intersection of the classes RP and Co-RP.

The definition of ZPP is based on probabilistic Turing machines. Other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.