derandomization
Suppose you have a wonderfully simple algorithm that works only because it flips real coins. A natural, almost greedy question follows: do you really need genuine randomness, or could you replace those coins with something deterministic and still be correct? Derandomization is the program of removing the randomness from a randomized algorithm without losing efficiency — turning a coin-flipping (BPP-style) algorithm into an ordinary deterministic one that runs in polynomial time.
The central engine of this program is the pseudorandom generator: a deterministic procedure that stretches a short truly-random seed into a long string of bits that 'looks random' to any efficient algorithm — meaning no fast test can tell the stretched bits from real coin flips. If such a generator exists and is itself efficient, you can feed its output to your randomized algorithm in place of real coins and get the same answer, then sweep over all possible short seeds deterministically. The astonishing result of this line of work (Impagliazzo and Wigderson, among others) is conditional but striking: if some problem in EXP genuinely needs exponential-size circuits — a very believable hardness assumption — then good pseudorandom generators exist, and therefore P = BPP. In a slogan, hardness yields randomness: the existence of hard problems lets us fake randomness perfectly.
This is why complexity theorists overwhelmingly believe P = BPP, that randomness adds no power to polynomial-time decision-making, even though it remains unproven. The belief reverses a once-natural intuition: people long assumed randomness was an extra resource, but it now looks like a convenience we could in principle do without. Note the honest caveats — this is a conjecture resting on a circuit-hardness assumption, it concerns decision problems and worst-case efficiency (not necessarily the same constant factors or the same elegance), and it does not say randomness is useless in cryptography or in sampling, where it plays a different, essential role.
PRIMES is a real-life success story of derandomization in spirit: for decades the only fast primality test was the randomized Miller-Rabin, but in 2002 the AKS algorithm gave a fully deterministic polynomial-time test, proving PRIMES is in P and removing the need for coins entirely for that one problem.
Derandomization aims to replace real coin flips with pseudorandom bits no fast test can distinguish.
P = BPP is conjectured, not proved; the strongest theorems are conditional ('if hard problems of a certain kind exist, then P = BPP'). And derandomizing for decision problems does not mean randomness is dispensable everywhere — it remains genuinely necessary for cryptography and for many sampling tasks.