The Karp–Lipton Theorem

Imagine you discovered a cheat sheet — a pocket-sized table — that, for any input of length n, tells you the answer to any NP problem in a single lookup. Such a cheat sheet might not be "computable" in the traditional sense, but it would be small: only polynomial in n. In complexity theory, the class of problems solvable with such advice is called P/poly — polynomial time with a polynomial-length hint.

For decades, researchers suspected that NP problems are not in P/poly: they should require exponentially large circuits, not small ones. Nobody has proved it — but in 1980, Richard Karp and Michael Lipton proved something just as striking from the other direction.

They showed that if you assume $\text{NP} \subseteq \text{P/poly}$ (i.e., every NP problem has polynomial-size circuits), a dramatic consequence follows: the entire polynomial hierarchy collapses to its second level. That is, $\text{PH} = \Sigma_2$. The elaborate tower of complexity classes above NP would all smash together into a single layer — a result most complexity theorists consider very unlikely. The Karp-Lipton theorem thus gives strong evidence that NP problems cannot have small circuits, without ever directly proving it.

The proof has three steps, each an implication. Walk through them one at a time — click Next step to see each step unfold and why it follows from the previous one.

<div class="kl-wrap">
  <div class="assumption-box" id="assumption">
    <span class="label">{{lbl_assumption}}</span>
    <strong>NP ⊆ P/poly</strong>
    <span class="sub">{{sub_assumption}}</span>
  </div>
  <div class="arrow-row" id="arrow0">
    <div class="arrow-line"></div>
    <div class="arrow-head">▼</div>
    <button id="btn0" class="next-btn" type="button">{{btn_next}} →</button>
  </div>
  <div class="step-box hidden" id="step1">
    <span class="label">{{lbl_step1}}</span>
    <strong>coNP ⊆ NP/poly</strong>
    <span class="sub">{{sub_step1}}</span>
  </div>
  <div class="arrow-row hidden" id="arrow1">
    <div class="arrow-line"></div>
    <div class="arrow-head">▼</div>
    <button id="btn1" class="next-btn" type="button">{{btn_next}} →</button>
  </div>
  <div class="step-box hidden" id="step2">
    <span class="label">{{lbl_step2}}</span>
    <strong>Σ₂ absorbs coNP</strong>
    <span class="sub">{{sub_step2}}</span>
  </div>
  <div class="arrow-row hidden" id="arrow2">
    <div class="arrow-line"></div>
    <div class="arrow-head">▼</div>
    <button id="btn2" class="next-btn" type="button">{{btn_see_result}} →</button>
  </div>
  <div class="result-box hidden" id="result">
    <span class="label result-label">{{lbl_conclusion}}</span>
    <strong>PH = Σ₂</strong>
    <span class="sub">{{sub_conclusion}}</span>
    <button id="resetBtn" class="reset-btn" type="button">↺ {{btn_reset}}</button>
  </div>
  <div class="hierarchy" id="hierarchy">
    <div class="hier-label">{{hier_title}}</div>
    <div class="hier-levels">
      <div class="hlevel" id="h-ph">PH = ⋯ ∪ Σ₃ ∪ Σ₂ ∪ Σ₁</div>
      <div class="hlevel" id="h-s3">Σ₃</div>
      <div class="hlevel" id="h-s2">Σ₂</div>
      <div class="hlevel" id="h-s1">Σ₁ = NP</div>
    </div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.kl-wrap { display: flex; flex-direction: column; gap: 0; align-items: stretch; padding: .5rem; }
.assumption-box, .step-box, .result-box {
  border-radius: 10px; padding: .7rem 1rem; display: flex; flex-direction: column; gap: .2rem;
  border: 2px solid #1d3557; background: #e8f0f7;
}
.result-box { border-color: #0a7d33; background: #e6f7ed; }
.label { font-size: .7rem; font-weight: 700; letter-spacing: .08em; text-transform: uppercase; color: #1d3557; }
.result-label { color: #0a7d33; }
.step-box strong, .assumption-box strong, .result-box strong { font-size: 1.1rem; color: #1d3557; }
.result-box strong { font-size: 1.3rem; color: #0a7d33; }
.sub { font-size: .82rem; color: #444; line-height: 1.4; }
.arrow-row { display: flex; flex-direction: column; align-items: center; gap: 0; padding: .1rem 0; }
.arrow-line { width: 2px; height: 14px; background: #1d3557; }
.arrow-head { color: #1d3557; font-size: 1.1rem; line-height: 1; }
.next-btn { margin-top: .3rem; font: 600 13px system-ui; padding: .35rem .8rem;
            background: #1d3557; color: #fff; border: none; border-radius: 7px; cursor: pointer; }
.next-btn:hover { background: #274472; }
.reset-btn { align-self: flex-start; margin-top: .5rem; font: 600 13px system-ui; padding: .35rem .8rem;
             background: #0a7d33; color: #fff; border: none; border-radius: 7px; cursor: pointer; }
.hidden { display: none !important; }
.hierarchy { margin-top: .8rem; border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .8rem; background: #f7f9fb; }
.hier-label { font-size: .72rem; font-weight: 700; text-transform: uppercase; letter-spacing: .07em; color: #888; margin-bottom: .4rem; }
.hier-levels { display: flex; flex-direction: column; gap: 3px; }
.hlevel { border-radius: 6px; padding: .25rem .5rem; font-size: .85rem; font-weight: 600;
          background: #dde6f0; color: #1d3557; transition: all .4s; text-align: center; }
.hlevel.collapsed { background: #0a7d33; color: #fff; transform: scaleY(0.7); }
.hlevel.hidden-level { opacity: 0; max-height: 0; overflow: hidden; margin: 0; padding: 0; }

// Code not found

Notice the structure: a single assumption ($\text{NP} \subseteq \text{P/poly}$) propagates through the hierarchy like a fault line, until the whole tower above NP is flattened. Each step is a real proof technique — advice strings, complementation, and the $\Sigma_2$ definition — not hand-waving. See P vs NP for why a collapsed hierarchy would be shocking.

The theorem's precise statement: if $\text{NP} \subseteq \text{P/poly}$, then $\text{PH} = \Sigma_2^p$ — proven by Richard Karp and Michael Lipton in 1980.

To unpack this, recall the polynomial hierarchy. Starting from NP (problems checkable in polynomial time), we build a tower:

• $\mathbf{\Sigma_1 = \text{NP}}$: problems solvable by a polynomial-time nondeterministic machine.
• $\mathbf{\Sigma_2}$: problems solvable with a polynomial-time machine that can call an NP oracle — asking NP questions for free.
• $\mathbf{\Sigma_3}$, $\mathbf{\Sigma_4}$, … each level sits one oracle query above the previous.
• PH = the union of all these levels.

Collapsing PH to $\Sigma_2$ means every problem in the entire infinite tower is already solvable at the second level — the levels above become redundant.

Why does $\text{NP} \subseteq \text{P/poly}$ cause the collapse? The proof goes in two steps.

Step 1 — $\text{coNP} \subseteq \text{NP/poly}$. If SAT (the canonical NP-complete problem) has polynomial-size circuits, then its complement UNSAT also has polynomial-size circuits (just flip the output bit). UNSAT is coNP-complete, so $\text{coNP} \subseteq \text{P/poly}$. Now NP can verify a coNP answer by guessing the right circuit as an advice string — giving $\text{coNP} \subseteq \text{NP/poly}$.

Step 2 — PH collapses to $\Sigma_2$. A classical theorem by Stockmeyer says: if $\text{coNP} \subseteq \text{NP}$, then $\text{PH} = \Sigma_2$. The NP/poly advice trick achieves exactly this relativized version. Every level of the hierarchy can be pulled down to $\Sigma_2$ using the circuit advice.

The contrapositive is equally important: if PH does not collapse (which nearly everyone believes), then $\text{NP} \not\subseteq \text{P/poly}$, meaning NP problems genuinely require exponentially large circuits. The theorem thus rules out entire families of approaches — any proof that P = NP via small circuits would simultaneously collapse the polynomial hierarchy. See the polynomial hierarchy for the broader context.

The Karp-Lipton theorem is not just a historical curiosity — it actively shapes modern complexity theory and its applications:

• Circuit lower bounds: The theorem motivates the quest to prove $\text{NP} \not\subseteq \text{P/poly}$ directly. Any such proof — showing that SAT needs exponentially large circuits — would be a breakthrough. The best known lower bounds (for monotone circuits) are exponential, but general circuit lower bounds for NP remain wide open.
• Cryptography: Many cryptographic hardness assumptions explicitly require that certain problems (like factoring) are hard even for circuits — i.e., they are not in P/poly. Karp-Lipton explains why this is the right notion of hardness for non-uniform adversaries. See factoring for a related discussion.
• Derandomization: The theory of pseudorandom generators (PRGs) is deeply linked to circuit lower bounds. If $\text{NP} \not\subseteq \text{P/poly}$ (as Karp-Lipton suggests is necessary), then strong PRGs exist and randomized algorithms can be derandomized.
• Oracle separations: The theorem provides a clean tool for separating complexity classes relative to oracles — if adding an oracle collapses the hierarchy, something structurally important is happening.
• Teaching complexity: Karp-Lipton is one of the best examples of a conditional lower bound — it shows that a common assumption (small circuits for NP) leads to a consequence (PH collapse) that would be incredibly surprising, giving indirect evidence against the assumption.

The pattern of "assume X, derive a collapse, conclude X is unlikely" is now a standard technique in complexity theory, and Karp-Lipton is its iconic prototype.

The Karp-Lipton theorem captures a beautiful tension at the heart of complexity theory: we cannot prove NP problems require large circuits, but we can show that small circuits would cause a catastrophe — the collapse of the entire polynomial hierarchy.

That catastrophe is considered so unlikely that the theorem functions as a proof by discomfort: nobody believes PH collapses, so nobody believes $\text{NP} \subseteq \text{P/poly}$, so we take the circuit lower bound as a working hypothesis even without a formal proof. This is the logic underlying much of modern cryptography and algorithm design.

The next time you hear a claim that NP problems might be "easy" with the right representation, remember Karp-Lipton: easy circuits for NP would not just solve hard problems — they would rewrite the entire map of computational complexity. And after forty years, that map has not been rewritten. See P vs NP for the open problem at the center of it all.