ZPP (complexity)

In computational complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is a complexity class. A problem is in ZPP if it has a probabilistic algorithm that always returns the correct answer, but whose expected running time is polynomial. In other words, a ZPP algorithm is a randomized algorithm that is always correct, and runs in polynomial time on average.

Equivalently, ZPP is the class of problems that can be solved by a Las Vegas algorithm with polynomial expected runtime. A Las Vegas algorithm is a randomized algorithm that either returns the correct result or reports that it has failed; it never returns an incorrect answer.

The class ZPP can also be defined using the classes RP and co-RP. Specifically:

ZPP = RP ∩ co-RP

Where:

• RP (Randomized Polynomial time) is the class of problems that have a probabilistic algorithm that runs in polynomial time. If the correct answer is "yes", the algorithm will return "yes" with probability at least 1/2. If the correct answer is "no", the algorithm will always return "no".
• co-RP is the class of problems whose complement is in RP. If the correct answer is "no", the algorithm will return "no" with probability at least 1/2. If the correct answer is "yes", the algorithm will always return "yes".

The intersection of RP and co-RP requires that for any instance of the problem, we can run both an RP algorithm and a co-RP algorithm. If either algorithm gives a definitive answer (e.g., the RP algorithm says "no", or the co-RP algorithm says "yes"), we know the correct answer. If both algorithms give a probabilistic answer (e.g., RP says "yes" with probability 1/2, and co-RP says "no" with probability 1/2), we can run both algorithms again. Since each run has a probability of at least 1/2 of giving a definitive answer, the expected number of runs until we get a definitive answer is polynomial. Since both algorithms run in polynomial time, the expected total running time is also polynomial.