Encyclopedia > ZPP

  Article Content

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Jamesport, New York

... is 2.88. In the town the population is spread out with 20.6% under the age of 18, 5.0% from 18 to 24, 26.8% from 25 to 44, 27.7% from 45 to 64, and 19.9% who are 65 years ...

 
 
 
This page was created in 25.6 ms