Circuit Complexity

Circuit complexity measures the computational resources required to compute a Boolean function using a network of logic gates (AND, OR, NOT). The two primary measures are size — the total number of gates — and depth — the length of the longest path from input to output. Circuit complexity offers a non-uniform model of computation: unlike a Turing machine, which uses a single finite program for all input lengths, a circuit family contains a different circuit for each input size. This non-uniformity makes circuit complexity both more powerful in principle and harder to bound.

The central open problem is whether NP-complete problems require superpolynomial circuit size. If any NP-complete problem can be solved by polynomial-size circuits, then the polynomial hierarchy collapses. The natural proofs barrier shows that standard combinatorial techniques cannot establish such lower bounds if strong pseudorandom generators exist, suggesting that proving circuit lower bounds may require entirely new mathematical frameworks.

Circuit complexity connects to computational complexity, proof complexity, and algebraic complexity — each offering a different lens on what makes problems hard.

The non-uniformity of circuit complexity is both its strength and its scandal: it allows circuits to encode arbitrary advice for each input length, yet we cannot prove that this extra power does not trivialize NP. The inability to separate polynomial-size circuits from NP is not a technical gap. It is a measure of how little we understand the boundary between structure and randomness in high-dimensional spaces.