2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Two-sided error seems pretty natural. For example, a court of law could find an innocent person guilty or a guilty person innocent. OK, that's not actually an algorithm but it illustrates the concept. $\endgroup$
    – David Richerby
    May 12, 2015 at 22:05
  • $\begingroup$ @DavidRicherby It sure is natural, but I'm looking for an actual algorithm that is used in practice. $\endgroup$
    – Christian Schnorr
    May 12, 2015 at 22:14
  • 1
    $\begingroup$ Clearly you are thinking as a mathematician/physicist and not an engineer (see "close enough for all practical purposes"). A cheap/fast solution with decent accuracy/optimality can be more valuable than an ideal solution (e.g., a perfect 2-days-from-data-collection weather forecast two weeks after data was collected is less useful — other than discovering issues with data and the model — than a 90% accurate forecast after only six hours). Inputs are never perfect, models are never perfect, goal definitions are never perfect. $\endgroup$
    – user4577
    May 13, 2015 at 2:00
  • $\begingroup$ @PaulA.Clayton I don't see how your weather forecast would be a probabilistic algorithm though. I would think of it as deterministic which might err nonetheless because our model is not sufficiently accurate enough and we can obviously not predict the future. Multiple runs would produce the same result over and over again and hence not increase the chance to not err. $\endgroup$
    – Christian Schnorr
    May 13, 2015 at 9:49
  • 1
    $\begingroup$ Data filtering for "interesting" information would be an obvious example of an application that could often tolerate error. The benefits of timely discovery of information may justify the cost of confirming postives and the lost opportunity cost of a few false negatives. Even for security applications (which would really prefer zero false negatives), timeliness of detection and low computational overhead are significant considerations. A secondary filter might provide minimum guarantees. $\endgroup$
    – user4577
    May 13, 2015 at 12:02

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for pointing me to the Monte Carlo thingy. In your oil example though, the algorithm doesn't simply accept or reject but instead returns one of the squares. Of course the error can be in whatever direction. I was thinking in terms of membership to a language $L$, where you have only two possible outcomes, and both of those could be flawed. $\endgroup$
    – Christian Schnorr
    May 15, 2015 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.