A language is in BPP if there is a probabilistic polynomial-time Turing machine such that for all x,
- If x is in L then the probability that M(x) accepts is at least 2/3.
- If x is not in L then the probability that M(x) accepts is at most 1/3.
A language is in RP if there is a probabilistic polynomial-time Turing machine such that for all x,
- If x is in L then the probability that M(x) accepts is at least 1/2.
- If x is not in L then the probability that M(x) accepts is 0.
A language is in ZPP if there is a probabilistic expected polynomial-time Turing machine such that for all x,
- If x is in L then the probability that M(x) accepts is 1.
- If x is not in L then the probability that M(x) accepts is 0.
We sketched why Composite testing is in RP and used Chernoff bounds to reduce the error in probabilistic algorithms to exponentially small. The exact statement of Chernoff bounds I gave in class was incorrect--we'll revisit on Friday.
Links:
- Computational Complexity of Probabilistic Turing Machines by John Gill. Defined the basic complexity classes.
- Miller-Rabin primality test - An RP algorithm for composite testing works even when you have Carmichael numbers.
- Primes in P by Agrawal, Kayal and Saxena
