Nisan-Wigderson Theorem

The Nisan-Wigderson Theorem (1994) is a foundational result in computational complexity establishing that sufficiently hard functions can be used to construct pseudorandom generators that fool polynomial-time algorithms. The theorem provides the central machinery for the derandomization program: if there exist problems in NP-complete or related classes that require exponentially large circuits to solve, then BPP = P, meaning all probabilistic polynomial-time algorithms can be simulated deterministically without significant slowdown. The result converts hardness into randomness, showing that computational difficulty in one domain generates structural simplicity in another — a pattern that recurs across complexity theory.

The theorem belongs to a broader family of hardness-randomness tradeoffs that form the backbone of modern complexity theory. Its proof technique — the hardness amplification and seed extension constructions — has been refined into subsequent results such as the Impagliazzo-Wigderson theorem, which achieves derandomization from weaker hardness assumptions. These results collectively suggest that randomness and computational difficulty are two faces of the same phenomenon, a duality that complexity theory has only begun to map.