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 unbounded, but on the 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. (Such an algorithm is called a Las Vegas algorithm.) 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 or 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.
- If the correct answer is YES, then it returns YES with probability at least 1/2.
- If the correct answer is NO, then it returns NO with probability at least 1/2.
The two definitions are equivalent.
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.
External link
- ZPP - from Complexity Zoo
Complexity classes
