$P=BPP$ Derandomization Conjecture

The conjecture asserts that randomness adds no essential power to feasible computation: $BPP$, the class of languages decided by probabilistic polynomial-time machines that answer correctly with probability at least $2/3$ on every input, equals $P$. Probabilistic polynomial-time computation was introduced by Gill in 1977 [Gill1977Probabilistic], and the derandomization form of the question took shape over the following decade as randomized algorithms proliferated.

The evidence for equality is largely conditional. The hardness-versus-randomness paradigm converts circuit lower bounds into pseudorandom generators strong enough to derandomize $BPP$; in particular, Impagliazzo and Wigderson proved that if some language in $E=\operatorname{DTIME}(2^{O(n)})$ requires circuits of size $2^{\Omega(n)}$, then $P=BPP$ [ImpagliazzoWigderson1997]. Unconditionally, $BPP$ is known to lie low in the polynomial hierarchy, inside $\Sigma_2\cap\Pi_2$, but no deterministic simulation of $BPP$ with only polynomial overhead has been established without unproven hypotheses [AroraBarak2009].

The conjecture is open. The known route to a proof runs through strong circuit lower bounds, themselves a central open frontier, so derandomization and hardness are now understood to be tightly linked.