Karp-Lipton Theorem

The Karp-Lipton Theorem is a foundational result in computational complexity theory that connects non-uniform computation to the collapse of complexity hierarchies. Proved by Richard Karp and Richard Lipton in 1980, the theorem states that if NP ⊆ P/poly — that is, if every problem in NP can be solved by polynomial-size circuits with polynomial advice — then the polynomial hierarchy collapses to its second level: PH = Σ₂P.

The theorem is remarkable because it shows that a seemingly mild form of non-uniformity (polynomial advice) would have catastrophic consequences for the entire structure of complexity theory. The polynomial hierarchy is believed to be an infinite tower of increasingly difficult classes; the Karp-Lipton Theorem says that even a small concession to non-uniformity would cause this tower to collapse to just two levels. This is why P/poly is viewed with suspicion: it is not merely a larger class than P, but a class whose containment of NP would rewrite the landscape of computability.

The proof technique is a self-reducibility argument. If SAT has polynomial-size circuits, then these circuits can be used to construct a Σ₂P algorithm for any problem in PH, by using the circuit to answer the existential queries that define the hierarchy. The circuit acts as a compressed oracle — it does not tell us how to solve NP problems uniformly, but it is enough to derandomize the existential quantifier and collapse the hierarchy.

The Karp-Lipton Theorem is often cited as evidence that NP is unlikely to have small circuits, and therefore that P ≠ NP is not merely a matter of uniform versus non-uniform computation. The theorem has been extended and strengthened: similar collapses follow if other classes are contained in P/poly, and the theorem has been adapted to probabilistic and quantum advice classes.

The Karp-Lipton Theorem is sometimes presented as a technical result about circuit complexity. It is more than that. It is a statement about the brittleness of complexity hierarchies: the entire edifice of computational difficulty rests on the assumption that non-uniformity does not trivialize the problems we believe are hard. If that assumption fails, the hierarchy does not merely bend — it shatters.