Randomized Complexity (BPP, RP)

Probabilistic machines, one- vs two-sided error, and amplification.

The idea

Randomized complexity classifies the problems a polynomial-time algorithm can solve when it may flip coins and be wrong with small probability. Randomized algorithms are often simpler and faster than any known deterministic algorithm for the same problem, so we study what the coins cost in correctness.

A probabilistic Turing machine runs in polynomial time and may flip fair coins, so on a fixed input its answer is a random variable. The standard classes differ in where the error may fall. $L$ is in $\mathbf{RP}$ when the error is one-sided: if $x \in L$ then $\mathbb{P}[\text{accept}] \ge \tfrac{1}{2}$, and if $x \notin L$ then $\mathbb{P}[\text{accept}] = 0$. $L$ is in $\mathbf{BPP}$ when the error is two-sided: the machine answers correctly with probability at least $\tfrac{2}{3}$ on every input, member or not. $L$ is in $\mathbf{ZPP}$ when the machine never errs and its running time is polynomial on average.

The constants $\tfrac{1}{2}$ and $\tfrac{2}{3}$ are arbitrary, because bounded error can be amplified: run the machine $k$ times independently and combine the answers, and the probability of a wrong verdict falls exponentially in $k$. The right way to combine the answers depends on where the error falls — one accepting run of an $\mathbf{RP}$ machine is already conclusive, while a $\mathbf{BPP}$ machine needs a majority vote. The figure plots the accept probabilities each definition allows on members and on non-members.

Ways to work on it

• Walkthrough. RP, BPP, ZPP and one-sided amplification by repetition.
• Practice. Read off what one run of a randomized machine certifies.
• Hardest. Bound the repetitions needed to amplify a two-sided-error BPP algorithm.

Not sure where to start? Take the ten-question placement test.