Impagliazzo-Wigderson Theorem

The Impagliazzo-Wigderson Theorem (1997) is a landmark result in computational complexity that strengthens the Nisan-Wigderson Theorem by achieving derandomization from significantly weaker hardness assumptions. Where the Nisan-Wigderson construction requires exponential circuit lower bounds, Impagliazzo and Wigderson showed that problems requiring only slightly superpolynomial circuits suffice to construct pseudorandom generators strong enough to derandomize all of BPP.

The theorem is a refinement of the hardness-randomness paradigm: it demonstrates that the gap between probabilistic and deterministic computation is not protected by a wall of computational difficulty, but by a fence that can be lowered. The proof technique — hardness amplification combined with direct product theorems — transforms weak hardness into strong hardness, which can then be converted into pseudorandomness via the Nisan-Wigderson framework.

The result is widely interpreted as evidence that P = BPP, though it falls short of a proof. It shows that the derandomization question is tightly coupled to the existence of hard problems in NP: if any problem in NP requires circuits of size n^ω(1), then every probabilistic polynomial-time algorithm can be simulated deterministically. The theorem thus converts a question about randomness into a question about the structure of computational difficulty.