Computing with Randomness: BPP

A machine that flips coins

Every machine you have met so far has been predictable: feed a Turing machine the same input twice and it does exactly the same thing both times, because each move is fixed by the rule delta(q, a) = p. This rung opens by handing that machine one new gadget — a fair coin. At any step it may flip the coin and branch on the result: heads do this, tails do that. The machine is still an honest, step-by-step computer with finite control and a tape; it has simply gained access to a stream of genuinely random bits. We call it a probabilistic machine, and the question of this guide is blunt: does letting a machine gamble ever let it solve problems faster?

Be careful not to confuse this coin-flipping with the nondeterminism of the earlier rungs. When an NFA or a nondeterministic Turing machine faces a choice, it conceptually clones itself and explores every branch at once, accepting if any branch accepts — a perfect, magical guesser with no notion of likelihood. A probabilistic machine has no clone army. It walks one path, choosing each fork by an actual coin toss, and the relevant quantity is the probability that this single run lands on the right answer. As the glossary stresses, nondeterminism is not randomness: nondeterminism asks "does a lucky path exist?", while randomness asks "is a path likely?". Those are very different questions, and they define very different classes.

Bounded error, made precise: BPP

Recall the class P: the yes/no problems a deterministic machine decides in polynomial time, our working stand-in for efficiently and exactly solvable. The randomized analogue is BPP, which stands for Bounded-error Probabilistic Polynomial time. A problem is in BPP if some probabilistic machine runs in polynomial time and, on every input, gives the correct yes/no answer with probability at least 2/3. The phrase "with probability at least 2/3" is the whole story: the machine is allowed to be wrong, but only with a bounded probability strictly better than a coin flip, on every single input — not just on most of them.

Why the oddly specific 2/3? Because the exact constant barely matters, and that is the beautiful part. Any fixed gap above 1/2 will do — 0.51, 2/3, 0.9 all define the same class — thanks to amplification. Run the machine many times on the same input and take a majority vote of the answers. Each run is an independent coin-driven trial biased toward the truth, so by the law of large numbers the majority is overwhelmingly likely to be right. A handful of independent runs already pushes the error from 1/3 down toward a few percent; a few hundred runs drive it below the chance of your computer being hit by a meteor mid-calculation. Crucially, the number of repeats needed to reach any target confidence is a constant (or grows only mildly), so polynomial time stays polynomial. That is exactly why we tolerate a coin-flipping machine being occasionally wrong: the error is not a fixed flaw, it is a dial we can turn down as far as we please for a modest, polynomial cost.

One-sided and zero-sided: RP and ZPP

BPP allows the machine to err in both directions — a true yes might be misreported as no, and vice versa. Often we can do better. The class RP (Randomized Polynomial time) is the one-sided version: when the true answer is no, the machine never errs — it always says no; when the true answer is yes, it says yes with probability at least 1/2 and may sometimes wrongly say no. This is the natural shape of a randomized search for a witness: a single yes-shout is trustworthy because the machine cannot manufacture a false yes, while a no-shout might just be bad luck that more tries would overturn.

Better still is ZPP (Zero-error Probabilistic Polynomial time), the home of Las Vegas algorithms: the answer is always correct, and only the running time is random. Picture an algorithm that keeps drawing random guesses until one is verifiably right — its output is never wrong, but you cannot promise exactly when it will finish, only that it finishes fast on average. Contrast this with the Monte Carlo style of BPP and RP, where the running time is fixed but the answer may be wrong. A clean mental slogan: Las Vegas always tells the truth but takes an uncertain amount of time; Monte Carlo always finishes on time but may lie a little. These classes nest cleanly: ZPP sits inside RP, RP sits inside BPP, and every deterministic P algorithm trivially counts as a randomized one that ignores its coins, so P is inside all of them.

  WORST-CASE BEHAVIOUR ON A SINGLE RUN

  class   true=YES            true=NO             time
  -----   -----------------   -----------------   --------------
  P       always YES          always NO           fixed, poly
  ZPP     always YES          always NO           random, poly avg   (Las Vegas)
  RP      YES w.p. >= 1/2      ALWAYS NO           fixed, poly        (Monte Carlo, 1-sided)
  BPP     YES w.p. >= 2/3     NO w.p. >= 2/3      fixed, poly        (Monte Carlo, 2-sided)

  nesting:   P  in  ZPP  in  RP  in  BPP
  amplify any of them: repeat + vote -> error shrinks fast, time stays poly

Where does BPP sit on the map?

Time to place BPP on the complexity-class map you have been building. We know P is inside BPP, since coins are an option you can decline. At the other end, BPP is contained in PSPACE: a polynomial-space machine can, in principle, loop over all possible coin-flip sequences one at a time, reusing the same scratch space, and tally how often the answer is yes — turning the probability into an exact count. So we have P inside BPP inside PSPACE. But where BPP sits relative to NP is genuinely murky: BPP is not known to be inside NP, nor NP inside BPP. The randomized coin-flipper and the lucky-guesser are different beasts, and how they compare is open.

Now for the twist that surprises almost everyone. For decades, randomness looked like a genuine extra resource: certain problems had fast randomized algorithms but no known deterministic one. The flagship was primality testing — deciding whether a number is prime — where the celebrated Miller-Rabin coin-flipping test ran circles around any deterministic method. So surely BPP is strictly bigger than P? Here is the shock: in 2002 the AKS algorithm put primality squarely into P with no coins at all, erasing the most famous gap. And the broader belief among complexity theorists today is even bolder: most conjecture that P equals BPP — that randomness, for decision problems, buys speed and simplicity but no fundamental power. If true, every BPP algorithm could in principle be made deterministic.

Derandomization: trading coins for hardness

The program that aims to prove P equals BPP is called derandomization: systematically removing the coins from a randomized algorithm while keeping it efficient. The central tool is a pseudo-random generator — a deterministic gadget that stretches a tiny truly-random seed into a long stream of bits that no efficient algorithm can tell apart from real coin flips. If such a generator exists, you can replace a BPP machine's expensive randomness with a cheap seed, then loop deterministically over all possible short seeds and take a majority vote. The randomness vanishes; the answer survives.

1. Start with a BPP algorithm M that, on input x, flips m random bits and answers correctly with probability at least 2/3.
2. Suppose we own a pseudo-random generator G that turns a short seed of length s (with s much smaller than m) into m bits that M cannot distinguish from true random ones.
3. Because M cannot tell G's output from real coins, running M on G's bits gives essentially the same answer probabilities as running it on real coins.
4. Now do the deterministic trick: loop over ALL 2^s short seeds, run M with each, and output the majority answer — no coins used, and 2^s stays small (polynomial) when s is logarithmic in the input size.
5. The result is a deterministic polynomial-time algorithm with the same answer — the randomized problem has been pushed into P.

So does such a pseudo-random generator exist? Here lies one of the most beautiful threads in modern complexity theory: a deep line of results (the hardness-versus-randomness connection) shows that strong enough computational hardness implies strong derandomization. Concretely, if some problem in EXP genuinely requires exponential-size circuits — a hardness assumption most theorists believe — then good pseudo-random generators exist and P equals BPP follows. The slogan is striking: *if hard problems really are hard, then randomness is powerless for decision problems.* But this is an implication, not a theorem about reality — it rests on an unproven hardness assumption. Whether P truly equals BPP remains one of the field's great open problems, woven into the same fabric as P versus NP.