47.03.02 · theoretical-cs / advanced-complexity

Circuit Complexity: P/poly and the Karp-Lipton Theorem

shipped3 tiersLean: none

Anchor (Master): Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §6.1-6.5 (P/poly, Karp-Lipton, Meyer's theorem P = PSPACE implies EXP is not in P/poly, circuit lower bounds for PARITY, AC0 bounds via Håstad's switching lemma)

Intuition Beginner

A computer program is a sequence of instructions executed one at a time. A Boolean circuit is a different way to compute: it is a web of connected logic gates that all fire simultaneously. Each gate takes its inputs, computes AND, OR, or NOT, and passes the result forward. No loops, no memory, no repeated steps — just a single pass from inputs to output.

The size of a circuit is the number of gates it contains. The depth is the longest path from any input to the output. A circuit family is an infinite sequence of circuits, one for each input length. If every circuit in the family has size bounded by a polynomial in the input length, the family is "polynomial-size."

The class P/poly consists of all languages that can be recognised by polynomial-size circuit families. This class contains all of P (because a polynomial-time computation can be "unrolled" into a circuit), but it also contains undecidable languages (because the circuit for each input length can encode arbitrary information about that length).

The big question is whether NP is contained in P/poly. The Karp-Lipton theorem says that if NP does have polynomial-size circuits, then the polynomial hierarchy collapses to its second level. Most complexity theorists believe the hierarchy does not collapse, so the theorem provides evidence that NP is not in P/poly — meaning some NP problems inherently require superpolynomial circuits.

Visual Beginner

A Boolean circuit computing the function $f (x_{1}, x_{2}, x_{3}) = (x_{1} \land x_{2}) \lor \neg x_{3}$ :

x_1 ──→ [AND] ──→ [OR] ──→ output
x_2 ──→ [AND]      ↑
x_3 ──→ [NOT] ─────┘

The circuit has 3 gates: one AND, one NOT, one OR. Size = 3. Depth = 2 (AND and NOT at depth 1, OR at depth 2).

Input (x1,x2,x3)	x1 AND x2	NOT x3	Output
(0,0,0)	0	1	1
(1,1,0)	1	1	1
(0,1,1)	0	0	0
(1,1,1)	1	0	1

Worked example Beginner

We show that a polynomial-time Turing machine (as defined in 42.04.01) can be simulated by a polynomial-size circuit.

Consider a TM that sorts three numbers. The TM runs in some fixed polynomial time $t (n)$ . For inputs of a fixed length $n$ , the computation is a sequence of $t (n)$ steps, each involving a bounded number of bits.

Unrolling the computation. Each step of the TM reads a bounded amount of information (current state, symbol under head) and produces a bounded amount of information (new state, written symbol, head direction). Each step can be computed by a constant-size circuit (a few AND, OR, NOT gates).

Chaining $t (n)$ such circuits gives a circuit for the entire computation. The total size is $O (t (n))$ , which is polynomial in $n$ . For each input length $n$ , we get a different circuit $C_{n}$ .

The catch is that the circuit is non-uniform: it can be different for each input length. A single algorithm (program) generates a family of circuits, but the circuits themselves can encode length-specific information.

Check your understanding Beginner

Formal definition Intermediate+

Definition (Boolean circuit). A Boolean circuit $C$ with $n$ input variables is a directed acyclic graph where:

Each node of in-degree 0 is an input gate labelled by a variable $x_{i}$ or a constant 0 or 1.
Each node of in-degree $\geq 1$ is a computation gate labelled by AND, OR, or NOT. AND and OR gates have in-degree 2, NOT gates have in-degree 1.
One node is designated the output gate.

The circuit computes a function $f : {0, 1}^{n} \to {0, 1}$ by evaluating gates in topological order.

Definition (circuit size and depth). The size of a circuit $C$ is the number of gates. The depth is the length of the longest directed path from any input to the output.

Definition (circuit family). A circuit family is a sequence ${C_{n}}_{n \geq 1}$ where $C_{n}$ has $n$ input gates. The family recognises a language $L$ if for every $x \in {0, 1}^{*}$ , $C_{∣ x ∣} (x) = 1 ⟺ x \in L$ .

Definition (P/poly). The class $P/poly$ is the set of languages recognised by circuit families ${C_{n}}$ where $∣ C_{n} ∣ \leq p (n)$ for some polynomial $p$ .

Equivalently, $P/poly = ⋃_{c} SIZE (n^{c})$ where $SIZE (s (n))$ is the class of languages recognised by circuit families of size $O (s (n))$ .

Definition (advice strings). An alternative characterisation: $L \in P/poly$ iff there exists a polynomial-time TM $M$ and a family of advice strings ${a_{n}}_{n \geq 1}$ with $∣ a_{n} ∣ \leq p (n)$ such that $x \in L ⟺ M (x, a_{∣ x ∣}) = 1$ .

The advice string $a_{n}$ encodes a description of the circuit $C_{n}$ . The polynomial-time bound applies to the TM, not to generating the advice — the advice can encode uncomputable information.

Counterexamples to common slips

"P/poly is bigger than P because circuits are faster." P/poly is bigger because it is non-uniform: different circuits for different input lengths can encode completely different algorithms or even uncomputable information. Speed is not the issue.
"If NP is in P/poly, then NP = P." The Karp-Lipton theorem gives a weaker conclusion: the polynomial hierarchy collapses to $Σ_{2}^{p}$ . The implication NP $\subseteq$ P/poly $\Rightarrow$ NP = P is not known to hold.
"Circuit lower bounds are easy because circuits are simple." Proving superpolynomial lower bounds for explicit functions is one of the hardest open problems in complexity theory. The best known lower bound for general circuits is about $5 n - o (n)$ (Iwama and Morizumi, 2002).

Key theorem with proof Intermediate+

Theorem (Karp-Lipton). If $NP \subseteq P/poly$ , then $PH = Σ_{2}^{p}$ .

Proof sketch. Suppose $NP \subseteq P/poly$ . Then SAT has a polynomial-size circuit family ${C_{n}}$ . We show $Σ_{2}^{p} = PH$ by showing $Π_{2}^{p} \subseteq Σ_{2}^{p}$ .

Consider a $Π_{2}^{p}$ language: $L = {x : \forall y \in {0, 1}^{p (∣ x ∣)} \exists z \in {0, 1}^{q (∣ x ∣)} R (x, y, z)}$ for polynomial-time decidable $R$ .

The inner predicate " $\exists z R (x, y, z)$ " is in NP (the witness $z$ is the certificate). Since NP $\subseteq$ P/poly, there is a polynomial-size circuit $C$ that, given $(x, y)$ , outputs a witness $z$ such that $R (x, y, z) = 1$ if one exists.

The circuit $C$ has polynomial size but is not known. Use self-reducibility of SAT to construct $C$ : given the first $i$ bits of a satisfying assignment, the remaining SAT instance is still in NP, so the circuit for it also exists. By searching bit by bit using $\exists$ quantification over the circuit family, we can express " $C$ exists and works correctly" as a $Σ_{2}$ statement.

Formally: $x \in L$ iff $\exists C$ (polynomial-size circuit) $\forall y$ : $C (x, y)$ is a valid witness and $R (x, y, C (x, y)) = 1$ . Since $C$ has polynomial size, it can be quantified over in $Σ_{2}$ . This places $L$ in $Σ_{2}^{p}$ . $□$

Bridge. The Karp-Lipton theorem is the foundational reason circuit upper bounds have consequences for the structure of complexity classes: if NP has small circuits, the polynomial hierarchy collapses. This builds toward the circuit lower bound program, where showing that specific functions require large circuits would separate complexity classes. The central insight is that self-reducibility of SAT — the ability to reconstruct a full solution from partial solutions — links the existence of circuits to the collapse of the hierarchy. This is exactly the technique that appears again in the proof that PARITY is not in AC0, where circuit lower bounds are proved by combinatorial methods. Putting these together yields a two-front approach to the P vs NP question: either find polynomial-size circuits for NP (collapsing PH) or prove superpolynomial lower bounds (separating P from NP), and the Karp-Lipton theorem is the bridge between these two possibilities.

Exercises Intermediate+

Exercise 5 (medium, short answer).

Explain the self-reducibility of SAT and why it is crucial for the Karp-Lipton theorem.

Answer

SAT is self-reducible because a formula $φ$ is satisfiable iff either $φ [x_{1} = 0]$ is satisfiable or $φ [x_{1} = 1]$ is satisfiable. Given a circuit that solves SAT, we can reconstruct a satisfying assignment bit by bit: for each variable $x_{i}$ , check whether the formula with $x_{i} = 0$ (and the previously fixed assignments) is satisfiable using the circuit. If yes, set $x_{i} = 0$ ; otherwise set $x_{i} = 1$ . This takes $n$ queries to the circuit, producing a full satisfying assignment. The Karp-Lipton theorem uses this to convert "there exists a circuit for SAT" (an existential statement) into "we can find and verify the circuit" (a $Σ_{2}$ statement), enabling the collapse of PH.

Exercise 6 (hard, symbolic).

Prove that if $EXP \subseteq P/poly$ then $EXP = Σ_{2}^{p}$ .

Hint

Use the fact that every EXP language has a polynomial-time verifier with exponential-size advice (the circuit). Show that quantifying over the circuit places the language in $Σ_{2}^{p}$ .

Answer

Let $L \in EXP$ decided by TM $M$ in time $2^{n^{k}}$ . If $EXP \subseteq P/poly$ , then $M$ has a polynomial-size circuit family ${C_{n}}$ with $∣ C_{n} ∣ \leq p (n)$ . The circuit $C_{n}$ can be described by $O (p (n)^{2})$ bits (encoding the DAG). To decide if $x \in L$ : guess the circuit $C_{∣ x ∣}$ (existential quantifier over $O (p (n)^{2})$ bits), then verify that $C$ correctly simulates $M$ on all inputs of length $n$ (universal quantifier over all $2^{n}$ inputs). The verification runs in polynomial time given $C$ . So $L \in Σ_{2}^{p}$ . Since $Σ_{2}^{p} \subseteq EXP$ , we get $EXP = Σ_{2}^{p}$ . Rubric: full credit for the double-quantifier argument.

Lean formalization Intermediate+

Mathlib has no formalisation of Boolean circuits, circuit families, P/poly, or the Karp-Lipton theorem. The foundational gap is the absence of a Circuit structure with gate types, size measurement, and a correctness predicate, and the definition of P/poly as a complexity class. The Karp-Lipton proof requires the self-reducibility of SAT and a formalisation of the polynomial hierarchy. This unit ships without a lean_module.

Advanced results Master

Three results form the foundation of circuit complexity theory.

Theorem 1 (Shannon's counting argument). Almost every Boolean function $f : {0, 1}^{n} \to {0, 1}$ requires circuits of size $Ω (2^{n} / n)$ .

The proof is a counting argument: there are $2^{2^{n}}$ functions but only $2^{O (s l o g s)}$ circuits of size $s$ . For $s = c \cdot 2^{n} / n$ with $c$ small enough, the number of circuits is smaller than the number of functions. This shows that hard functions exist but does not construct one explicitly ^{[Arora & Barak §6.1]}.

Theorem 2 (PARITY is not in AC0). The parity function $PARITY_{n} (x) = x_{1} \oplus x_{2} \oplus \dots \oplus x_{n}$ cannot be computed by circuit families of constant depth and polynomial size (i.e., PARITY $\in /$ AC0).

This was proved by Furst, Saxe, and Sipser (1984) and independently by Ajtai (1983), using the method of random restrictions. Håstad (1986) strengthened the result with his switching lemma, showing that any AC0 circuit for PARITY requires exponential size. This was the first major circuit lower bound and remains one of the strongest.

Theorem 3 (Karp-Lipton for EXP). If $EXP \subseteq P/poly$ then $EXP = Σ_{2}^{p}$ .

This stronger version of the Karp-Lipton theorem uses the same self-reducibility argument. The implication is that proving EXP is not in P/poly (which would follow from P $\neq =$ NP by Meyer's theorem) would show that EXP is strictly above $Σ_{2}^{p}$ .

Synthesis. Circuit complexity is the foundational reason we can hope to separate complexity classes by combinatorial methods: circuit lower bounds on explicit functions imply class separations. The central insight is that circuits are a non-uniform model — different circuits for different input lengths — and this is exactly what makes them both powerful enough to contain P and weak enough to be attacked by counting arguments. This builds toward the AC0 lower bounds and the Razborov-Smolensky results for AC0[p], where algebraic methods prove that modular counting functions require large constant-depth circuits. Putting these together with the Karp-Lipton theorem yields a two-front strategy: circuit upper bounds collapse the hierarchy, and circuit lower bounds separate classes, and the bridge is that self-reducibility converts existential circuit claims into verifiable ones.

Full proof set Master

Proposition 1 (P is contained in P/poly). $P \subseteq P/poly$ .

Proof. Let $L \in P$ decided by TM $M$ running in time $t (n) = n^{k}$ . For each input length $n$ , construct a circuit $C_{n}$ that simulates $M$ on all inputs of length $n$ . The computation tableau of $M$ is a $t (n) \times t (n)$ grid. Each cell in row $i + 1$ depends on at most 3 cells in row $i$ (the cell above and its two neighbours, by the locality of the TM transition function). Each row transition can be computed by a circuit of size $O (1)$ per cell, giving $O (t (n))$ per row. With $t (n)$ rows, the total circuit size is $O (t (n)^{2}) = O (n^{2 k})$ , which is polynomial in $n$ . The circuit family ${C_{n}}$ recognises $L$ , so $L \in P/poly$ . $□$

Proposition 2 (Karp-Lipton theorem). If $NP \subseteq P/poly$ then $PH = Σ_{2}^{p}$ .

Proof. Assume NP $\subseteq$ P/poly. We show $Π_{2}^{p} \subseteq Σ_{2}^{p}$ , which implies PH collapses to $Σ_{2}^{p}$ (since $Σ_{2}^{p}$ is closed under complement when PH collapses).

Let $L \in Π_{2}^{p}$ : $x \in L ⟺ \forall y \exists z R (x, y, z)$ where $R$ is polynomial-time decidable and $∣ y ∣, ∣ z ∣$ are polynomial in $∣ x ∣$ . The predicate $ϕ (x, y) = \exists z R (x, y, z)$ is in NP.

Since NP $\subseteq$ P/poly, there exists a polynomial-size circuit family ${C_{n}}$ such that $C_{p (∣ x ∣)} (x, y)$ outputs a witness $z$ with $R (x, y, z) = 1$ whenever one exists. The circuit $C_{p (∣ x ∣)}$ has size $\leq q (∣ x ∣)$ for some polynomial $q$ .

Using self-reducibility: $x \in L ⟺ \exists C$ (of size $\leq q (∣ x ∣)$ ) $\forall y$ : $R (x, y, C (x, y))$ . The existential quantifier ranges over circuits of polynomial size (polynomially many bits to describe), and the universal quantifier ranges over polynomial-length strings. Both quantifiers are polynomially bounded, so $L \in Σ_{2}^{p}$ . $□$

Proposition 3 (counting lower bound). There exist functions $f : {0, 1}^{n} \to {0, 1}$ requiring circuits of size at least $2^{n} / (3 n)$ .

Proof. The number of circuits of size $s$ with $n$ inputs is bounded by $2^{O (s (l o g s + l o g n))}$ : each of the $s$ gates is chosen from {AND, OR, NOT} and has at most $s + n$ possible inputs. For $s = 2^{n} / (3 n)$ , this bound is at most $2^{2^{n} /3}$ . Since there are $2^{2^{n}}$ functions, at most a $2^{- 2 \cdot 2^{n} /3}$ fraction have circuits of size $\leq 2^{n} / (3 n)$ . Hence most functions require larger circuits. $□$

Connections Master

47.02.01 — P and NP are the starting point for circuit complexity; P/poly is a non-uniform extension of P that contains P and some undecidable languages.
47.02.02 — The Cook-Levin tableau encoding is used in the proof that P is in P/poly; the Karp-Lipton theorem extends NP-completeness to the circuit setting.
47.03.01 — BPP is contained in P/poly (Adleman's theorem), connecting circuit complexity to derandomization.
42.04.01 — The Turing machine model is the uniform counterpart to circuits; the unrolling construction converts TM computations into circuits.

Historical & philosophical context Master

Circuit complexity emerged as a major research area in the 1970s, motivated by the hope that circuit lower bounds could resolve the P vs NP question. The Shannon counting argument (1949) showed that most functions require exponential-size circuits, but finding an explicit hard function proved extraordinarily difficult ^{[Arora & Barak §6.1]}.

The Karp-Lipton theorem (1980) was a breakthrough because it showed that circuit upper bounds have structural consequences: if NP has small circuits, the polynomial hierarchy collapses. This provided the first link between non-uniform complexity (circuits) and uniform complexity (TMs).

The PARITY lower bound by Furst, Saxe, and Sipser (1984) and Ajtai (1983) was the first superpolynomial lower bound for an explicit function against a natural circuit class (AC0). Razborov (1985) and Smolensky (1987) extended this to AC0[p], showing that modular counting requires superpolynomial size in constant-depth circuits with mod-p gates. These results remain among the strongest circuit lower bounds known, and the difficulty of extending them to general circuits (bypassing the "natural proofs" barrier of Razborov and Rudich, 1994) is one of the central obstacles in complexity theory ^{[Arora & Barak §6.5]}.

Bibliography Master

@book{arora2009,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{karp1980some,
  author  = {Karp, Richard M. and Lipton, Richard J.},
  title   = {Some Connections between Nonuniform and Uniform Complexity Classes},
  journal = {Proceedings of the 12th Annual ACM Symposium on Theory of Computing},
  pages   = {302--309},
  year    = {1980},
}
@article{furst1984parity,
  author  = {Furst, Merrick L. and Saxe, James B. and Sipser, Michael},
  title   = {Parity, Circuits, and the Polynomial-Time Hierarchy},
  journal = {Mathematical Systems Theory},
  volume  = {17},
  pages   = {13--27},
  year    = {1984},
}
@article{hastad1986computational,
  author  = {H{\aa}stad, Johan},
  title   = {Computational Limitations for Small-Depth Circuits},
  year    = {1986},
  note    = {PhD thesis, MIT},
}

Prerequisites

47.02.01
47.02.02

Tier anchors

beginner: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §6.1 (Boolean circuits as a hardware model of computation, circuit families recognising languages, the class P/poly of languages with polynomial-size circuits)
intermediate: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §6.1-6.3 (formal circuit definition, P/poly, advice strings, Karp-Lipton theorem: if NP is in P/poly then PH collapses to Sigma_2, circuit lower bounds)
master: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §6.1-6.5 (P/poly, Karp-Lipton, Meyer's theorem P = PSPACE implies EXP is not in P/poly, circuit lower bounds for PARITY, AC0 bounds via Håstad's switching lemma)

References

Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Section 6.1 defines a Boolean circuit as a directed acyclic graph where each gate computes AND, OR, or NOT of its inputs; a circuit family ${C_{n}}_{n \geq 1}$ recognises a language $L$ if $C_{n} (x) = 1$ iff $x \in L$ for all $∣ x ∣ = n$ ; the class $P/poly$ consists of all languages recognised by circuit families of size $p (n)$ for some polynomial $p$ ; Section 6.2 proves that $P \subseteq P/poly$ (every polynomial-time TM can be simulated by polynomial-size circuits by unrolling the computation tableau) and that P/poly contains undecidable languages (via advice strings); Section 6.3 proves the Karp-Lipton theorem: if $NP \subseteq P/poly$ then $PH = Σ_{2}^{p}$ , by using the self-reducibility of SAT to find a satisfying assignment using the polynomial-size circuit as advice.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m