Randomised Complexity Classes

For decades the fastest way to ask "is this 300-digit number prime?" was to flip coins. The Miller–Rabin test picks a random witness, runs a quick check, and declares "probably prime" or "definitely composite." Run it, and it might be fooled. Run it twenty times with fresh random witnesses, and the chance of being fooled every time drops below one in a million million — smaller than the odds of a cosmic ray flipping the answer in your RAM. Randomness bought a spectacular speed-up in exchange for a controllable sliver of doubt.

Once algorithms are allowed to toss coins, the tidy world of P and NP sprouts a family of randomised complexity classes, each defined by what kind of error it tolerates and how much. This page maps that family — RP, coRP, ZPP, BPP — and asks the question that haunts it: does randomness actually give more power, or merely more convenience?

One-sided error: RP and coRP

A randomised polynomial-time algorithm decides a problem while consulting a stream of random bits (each outcome treated as an independent fair coin). The gentlest kind errs on only one side.

\mathrm{RP} (randomised polynomial time): if the true answer is YES, the algorithm accepts with probability \ge \tfrac12; if the true answer is NO, it always rejects. So a YES from the algorithm is certain to be correct — no false positives — but a NO might be a fluke.
\mathrm{coRP} is the mirror image: no false negatives. A NO is certain; a YES might be a fluke. (\mathrm{coRP} is the complement class, exactly as coNP mirrors NP.)
The constant \tfrac12 is not sacred — any fixed gap works, because we can amplify it, next.

Miller–Rabin is the poster child: a composite number is always reported composite (a genuine witness never lies about compositeness), while a prime is reported "probably prime" with high probability — one-sided error, of the \mathrm{coRP} flavour for the predicate "is prime."

Probability amplification: turning a hunch into near-certainty

A single RP run has error \le \tfrac12 on YES-instances. Run it k times with fresh coins and accept if any run accepts. Since a NO-instance never accepts, the only way to be wrong is for all k runs to miss a YES — and, the runs being independent, that has probability at most

\left(\tfrac12\right)^{k} = 2^{-k}.

Twenty runs shrink the error below 10^{-6}; fifty, below 10^{-15}. The error decays exponentially in the number of runs, so a polynomial number of repetitions crushes it to astronomically small — while the total time stays polynomial. This one trick is why the exact starting constant never matters: any non-trivial advantage amplifies to as much confidence as you like.

For BPP (below), where both sides can err, you amplify by majority vote over many runs; the Chernoff bound shows the majority is wrong with probability again exponentially small in the number of trials.

Zero error and two-sided error: ZPP and BPP

\mathrm{ZPP} (zero-error probabilistic polynomial time): algorithms that never give a wrong answer but whose running time is random, with expected polynomial time. These are the Las Vegas algorithms — always right, usually fast. Cleanly, \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}: if you have both a no-false-positive and a no-false-negative test, run them together until one gives a certain answer.
\mathrm{BPP} (bounded-error probabilistic polynomial time): the most permissive — two-sided error, wrong with probability \le \tfrac13 on every instance, YES or NO. The \tfrac13 just needs to be a constant bounded away from \tfrac12; majority-vote amplification does the rest. BPP is the class most people mean by "efficiently solvable with randomness."

RP and coRP are the one-sided algorithms (Monte Carlo, fixed time, possible error); ZPP is the always-correct Las Vegas style; BPP is the two-sided Monte Carlo umbrella over all of them. Their inclusions form a clean chain:

\mathrm{P} \subseteq \mathrm{ZPP} \subseteq \mathrm{RP} \subseteq \mathrm{BPP}, \qquad \mathrm{RP} \subseteq \mathrm{NP}.

The error profiles at a glance

The whole family is distinguished by a single question asked twice — can it err when the true answer is YES, and when it is NO? This table is the map worth memorising.

Class	If true answer is YES	If true answer is NO	Error style	Shrink error by…
\mathrm{P}	always correct	always correct	deterministic (no error)	— (none needed)
\mathrm{RP}	accepts w.p. \ge \tfrac12 (may err)	always rejects (no false positive)	one-sided (Monte Carlo)	repeat, accept if any accepts
\mathrm{coRP}	always accepts (no false negative)	rejects w.p. \ge \tfrac12 (may err)	one-sided (Monte Carlo)	repeat, reject if any rejects
\mathrm{ZPP}	always correct	always correct	zero-error, random time (Las Vegas)	— (time is expected-poly)
\mathrm{BPP}	correct w.p. \ge \tfrac23	correct w.p. \ge \tfrac23	two-sided (Monte Carlo)	repeat, take majority vote

Read down the two middle columns: RP has a clean NO-column, coRP a clean YES-column, ZPP both columns clean, and BPP allows a little slack in both — the exact taxonomy the class names encode.

How much power does randomness really add?

Surprisingly little, as far as anyone can tell. BPP sits low in the landscape and is squeezed from several directions:

\mathrm{BPP} \subseteq \Sigma_2^{\mathrm{P}} \cap \Pi_2^{\mathrm{P}} (the Sipser–Gács–Lautemann theorem): BPP falls inside the second level of the polynomial hierarchy, so \mathrm{BPP} \subseteq \mathrm{PH} — randomness does not escape the hierarchy.
\mathrm{BPP} \subseteq \mathrm{P/poly} (Adleman's theorem): every BPP problem has polynomial-size circuits — a fixed "advice" string per input length can replace the coins entirely.
Together these say randomness, if powerful, is only mildly so — you cannot use it to leap above the second level of PH.

The modern belief goes further: randomness adds no asymptotic power at all. The derandomisation conjecture holds that \mathrm{P} = \mathrm{BPP} — every efficient randomised algorithm can be simulated by an efficient deterministic one. Deep work (Impagliazzo–Wigderson) shows that if certain natural problems require exponential-size circuits — very plausible — then strong enough pseudorandom generators exist to fool any BPP algorithm, and \mathrm{P} = \mathrm{BPP} follows. Hardness, paradoxically, would buy us derandomisation.

The clinching piece of evidence is historical. Primality was the flagship problem that only randomness seemed to solve efficiently — until the 2002 AKS algorithm proved \mathrm{PRIMES} \in \mathrm{P} deterministically. The one problem everyone pointed to as "randomness is essential here" turned out not to need it. That is why most theorists now bet the whole class BPP collapses down to P.

Amplification by majority vote only works if each run has a genuine, fixed advantage over a coin flip. If an algorithm were merely correct with probability \tfrac12 + \tfrac{1}{2^n} — technically better than half, but by a vanishing margin — you would need exponentially many repetitions to make the majority reliable, blowing the polynomial time budget. Demanding a constant gap (like \tfrac23 vs \tfrac13) guarantees the Chernoff bound kicks in and a polynomial number of votes suffices. So "bounded-error" means bounded away from \tfrac12 by a constant — the boundedness, not the exact value, is the whole point, and it is exactly what lets any constant in (\tfrac12, 1) be amplified to 1 - 2^{-n}.

The classic mix-up is to think all randomised algorithms "might give the wrong answer." Not so — it depends on what is random. A Monte Carlo algorithm (RP, coRP, BPP) has a fixed running time but a chance of a wrong answer. A Las Vegas algorithm (ZPP) is the opposite: it is never wrong, but its running time is the random quantity, guaranteed only in expectation. Randomised QuickSort is Las Vegas — always sorts correctly, occasionally slow; Miller–Rabin is Monte Carlo — always fast, occasionally fooled. When someone says "it's a randomised algorithm," always ask: is the answer random, or is the time?