When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but the standard randomized algorithms don't admit a simple description (or proof of correctness) in a lay-atmosphere. I often resort to the saying that randomized algorithms allow "finding hay in a haystack", but that has little mathematical substance.
The question: Is there a good example of a problem that:
-
is easily explained (and sufficiently interesting)
-
has a simple randomized algorithm
-
appears non-trivial to get an efficient deterministic algorithm
and ideally also satisfies:
- the randomized algorithm has a somewhat understandable proof of correctness – so no Markov/Chernoff/random-walk-mixing-times
Best Answer
Michael, how about approximating the volume of some shape in $\Re^n$ by sampling random points?
This example has the following advantages:
It seems easy enough to explain at a cocktail party (depending, of course, on the guests).
It's used constantly in "real life" (indeed, pretty much any Monte Carlo simulation in physics, etc. could be interpreted as solving this problem).
We don't know how to derandomize it. Indeed, the problem is easily seen to be PromiseBPP-complete (assuming of course that whether a point $x \in \Re^n$ belongs to the shape is decidable in polynomial time).