Problem Detail: 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.
Asked By : Christian Schnorr
Answered By : Yuval Filmus
Monte Carlo methods are inherently not one-sided, though it’s dubious whether they’re usually two-sided. The general idea is that in order to estimate the expectation of a random variable $X$, we take the average of many samples of $X$. For example, suppose that you’re a petroleum company, and you’re trying to decide where to look for oil. For every square in some grid you have some random variable $X_i$, expressing the probability that there is oil in square $i$, that you can estimate using your (noisy) data. You have some threshold $theta$ in mind, and will start drilling in every square $i$ for which $X_i geq theta$. Using a Monte Carlo algorithm (say, simulating the geological history of the area), you can determine $X_i$ up to some error $epsilon$. This translates to a two-sided error algorithm. You can also think of computation in general as having two-sided error. Hardware errors occur with extremely low probability, and they can affect the answer in every which way.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42486 Ask a Question Download Related Notes/Documents
