I am currently studying probabilistic algorithms and came across three major complexity classes:
- BPP: worst-case polynomial time, two-sided error
- RP: worst-case polynomial time, one-sided error
- ZPP: average-case polynomial time, no error
At first I couldn't understand why one would use an algorithm that could err. I figured it does make sense in some cases though, like primality testing for RSA encryption. The algorithm used there has a one-sided error only, though.
Even after hours of thinking about it, I failed to think of an algorithm with two-sided error that actually makes sense and could be / is used in practice.
Any pointers would be greatly appreciated.