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 unbounded, but on the average is polynomial
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.
Important complexity classes |
P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |