Symptom

You need to test whether two arithmetic circuits compute the same polynomial. The deterministic approach is to expand both into normal form, and the expansion is exponentially large.

The randomized approach takes four lines. Pick a random point, evaluate both circuits there, compare. If they differ as polynomials, the Schwartz-Zippel lemma says a random point catches it with probability at least $1 - d/|S|$. Repeat a few times and the error is negligible.

This is a pattern you have seen throughout Part II. Randomized quicksort dodges adversarial inputs. Miller-Rabin tests primality in milliseconds. Randomized load balancing beats every deterministic scheme you could tune by hand. Random sampling turns intractable counting into an estimate with a confidence interval.

So randomness is clearly powerful. It solves problems you do not know how to solve deterministically.

Except almost every complexity theorist believes it adds no power at all, and the reason is genuinely strange: whether you can eliminate randomness depends on whether hard problems exist. Not “hard problems make derandomization harder” — the opposite. Hardness is the resource that buys you fake randomness, and if computation is easy, randomness becomes irreplaceable.

Statement

$\mathsf{BPP}$ is the class of languages decidable by a probabilistic polynomial-time machine with error probability at most $1/3$ on every input.

Conjecture: $\mathsf{P} = \mathsf{BPP}$. Randomness does not extend what is efficiently computable.

Theorem (Impagliazzo-Wigderson, 1997): If some language in $\mathsf{E}$ requires circuits of size $2^{\Omega(n)}$, then $\mathsf{P} = \mathsf{BPP}$.

If there exists $L \in \mathsf{DTIME}(2^{O(n)})$ and $\epsilon > 0$ such that $L$ requires circuits of size $2^{\epsilon n}$ almost everywhere, then $\mathsf{P} = \mathsf{BPP}$.

Read the conditional carefully, because the direction is the surprise. A statement that something is hard implies that randomized algorithms can be made deterministic. Hardness is not the obstacle. Hardness is the input.

The reason $1/3$ in the definition is not arbitrary but also not special: amplification makes any constant below $1/2$ equivalent. Run the algorithm $k$ times and take the majority. Chernoff (T008) gives exponential decay in $k$, and the concrete numbers make it vivid: one run with error $1/3$; majority of 11 runs gives error $0.122$; 41 runs gives $0.0135$; 101 runs gives $2.7 \times 10^{-4}$; 301 runs gives $1.3 \times 10^{-9}$. To push below $2^{-100}$ takes 1121 runs — a constant factor, which is why the error bound in the definition carries no information.

Argument

Why anyone believes $\mathsf{P} = \mathsf{BPP}$. Two pieces of evidence.

First, problems keep getting derandomized. Primality was the flagship randomized-only problem for thirty years until Agrawal, Kayal, and Saxena gave a deterministic polynomial algorithm in 2002. Undirected connectivity was randomized-only until Reingold’s 2004 log-space algorithm. The list of problems that genuinely need randomness keeps shrinking, and the biggest survivor, polynomial identity testing, is exactly the one known to be equivalent to circuit lower bounds.

Second, and more decisively, the conditional theorem’s hypothesis is very weak. Everyone believes $\mathsf{E}$ contains hard problems — it would be astonishing if every exponential-time language had subexponential circuits. So almost everyone believes the conclusion.

The mechanism: hardness to pseudorandomness. This is the construction worth carrying away.

A pseudorandom generator stretches $\ell$ truly random bits into $m \gg \ell$ bits that no small circuit can distinguish from random. If you have one with $\ell = O(\log m)$, you derandomize completely: enumerate all $2^{\ell} = \text{poly}(m)$ seeds, run the algorithm on each, take the majority. Polynomial time, no randomness.

Nisan and Wigderson showed how to build the generator from a hard function $f$. Take the seed, extract many subsets of its bits using a combinatorial design in which any two subsets overlap in few positions, and output $f$ applied to each subset. If some circuit distinguished this output from random, you could convert that distinguisher into a small circuit computing $f$ — the design’s low overlap is what makes the reconstruction possible — contradicting $f$’s hardness.

Impagliazzo and Wigderson closed the remaining gap. Nisan-Wigderson needed $f$ to be hard on average, which is a strong assumption; IW showed worst-case hardness suffices, via hardness amplification using error-correcting codes. Encoding a worst-case-hard function with a suitable code produces one that is hard on average, because a good average-case algorithm would be a decoder.

$$\text{worst-case hard} \xrightarrow{\ \text{codes}\ } \text{average-case hard} \xrightarrow{\ \text{NW}\ } \text{PRG} \xrightarrow{\ \text{enumerate}\ } \mathsf{P} = \mathsf{BPP}$$

The converse, which makes it a genuine equivalence. Kabanets and Impagliazzo proved in 2004 that derandomizing polynomial identity testing implies circuit lower bounds. So you cannot derandomize without proving hardness, and the two problems are the same problem. This is why $\mathsf{P} = \mathsf{BPP}$ is believed but unproven: proving it requires circuit lower bounds, and T030 explains why those are hard to come by.

The five worlds, because they make the trade concrete. Impagliazzo’s 1995 framing is the standard way to hold what depends on what. Each world is a consistent possibility given current knowledge, and which one we live in determines both cryptography and derandomization at once.

  • Algorithmica. $\mathsf{P} = \mathsf{NP}$. Optimization is free, and every cryptographic primitive fails. No PRGs, so randomness is not eliminable by this route.
  • Heuristica. $\mathsf{P} \ne \mathsf{NP}$ but NP problems are easy on average. No cryptography, since hardness on random instances is what encryption needs.
  • Pessiland. Hard instances exist but nobody can generate them with known solutions. The worst world: no cryptography and no efficient algorithms.
  • Minicrypt. One-way functions exist, so symmetric cryptography and PRGs work, but public-key does not.
  • Cryptomania. Trapdoor functions exist. Public-key cryptography, secure multiparty computation, everything we currently deploy.

We behave as though we live in Cryptomania, and the entire internet is built on that assumption. Note what this post adds: in Minicrypt and Cryptomania, hardness is abundant, PRGs exist, and $\mathsf{P} = \mathsf{BPP}$ follows. In Algorithmica and Heuristica, hardness is scarce and derandomization by this construction is unavailable.

So the same fact that secures your TLS session is the fact that makes randomized algorithms dispensable. Cryptographers and complexity theorists are betting on identical propositions with opposite hopes, and that is the cleanest statement of why hardness is a resource rather than an obstacle.

Forbids

Derandomization without hardness. By Kabanets-Impagliazzo, a proof that $\mathsf{P} = \mathsf{BPP}$ yields circuit lower bounds. There is no easy route.

A world with both easy computation and unavoidable randomness. If everything in $\mathsf{E}$ has small circuits, no PRG of this kind exists. Hardness and derandomizability rise and fall together.

Randomness as a source of computational power in the usual sense. Under the believed hypothesis, $\mathsf{BPP}$ collapses to $\mathsf{P}$ and every randomized algorithm has a deterministic equivalent within a polynomial factor.

Cryptography in a world without hard problems. The same construction that yields PRGs yields pseudorandom functions, so if $\mathsf{E}$ has small circuits, cryptography as we know it fails. This is Impagliazzo’s “Algorithmica” world, and it is the same trade viewed from the other side.

Does not forbid

It does not mean randomized algorithms are pointless, and dropping them because “$\mathsf{P} = \mathsf{BPP}$ anyway” is the misreading that would cost you the most in practice. The derandomization is polynomial-time but the polynomial is dreadful, and no one implements it. Randomized quicksort, Miller-Rabin in OpenSSL and GnuPG, Monte Carlo integration, randomized routing, and hash-based load balancing are all faster, simpler, and more robust than their deterministic counterparts. $\mathsf{P} = \mathsf{BPP}$ is a statement about asymptotic classes and not about what to write.

It does not apply to the interactive or space-bounded settings. Randomness is provably powerful in interactive proofs — that is IP = PSPACE (T036) — and $\mathsf{RL}$ versus $\mathsf{L}$ remains open. The collapse is specific to polynomial time.

It does not mean true randomness is unnecessary for cryptography. Very much the opposite: the same theory says cryptographic PRGs require hardness assumptions, and a PRG seeded predictably is broken. The Debian OpenSSL bug of 2008 reduced the entropy pool to the process ID, generating 32,767 possible keys total. The Sony PS3 ECDSA break came from a reused nonce. Both are the theorem’s warning in production, and both cost far more than any asymptotic question.

It does not forbid quantum speedups. $\mathsf{BQP}$ is a different class, and Shor’s algorithm is not evidence about $\mathsf{BPP}$ at all. Quantum advantage, if it exists, comes from interference rather than randomness.

It does not say the hypothesis is proven. No superpolynomial circuit lower bound is known for any explicit function in $\mathsf{NP}$ — the record is about $5n$ gates. The strongest evidence for $\mathsf{P} = \mathsf{BPP}$ rests on an assumption nobody can currently establish, and honesty about that is part of understanding the result.

Boundary

The class landscape around $\mathsf{BPP}$ is worth holding precisely:

  • $\mathsf{RP}$ and $\mathsf{coRP}$ — one-sided error. Miller-Rabin is $\mathsf{coRP}$: a composite verdict is certain, a prime verdict is probable.
  • $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$ — always correct, expected polynomial time. Las Vegas rather than Monte Carlo.
  • $\mathsf{BPP}$ — two-sided error, and the class in question.
  • $\mathsf{PP}$ — error just under $1/2$, and much larger; $\mathsf{PP}$ contains $\mathsf{NP}$, so the gap in the error bound matters enormously.

Known unconditionally: $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$ (Adleman), and $\mathsf{BPP} \subseteq \Sigma_2 \cap \Pi_2$ (Sipser-Gács-Lautemann). So $\mathsf{BPP}$ is not wildly large. What is not known is whether $\mathsf{BPP} \subseteq \mathsf{NP}$, which is a good calibration point for how little is settled here.

The lasting idea is the exchange rate. Randomness and hardness are convertible: a hard function is a randomness generator, and a distinguisher is an algorithm. Once you see that, cryptography and derandomization stop being separate subjects and become the same theorem read in two directions.