Introduction to Circuit Complexity

We have been thinking of computation as a process: a machine that reads, writes, and moves, one step at a time. The computation unfolds in time, and you cannot see where it is going until it gets there.

There is another way to think about computation. Instead of a process, imagine a structure: inputs on one side, an answer on the other, and in between a network of simple operations wired together. No tape, no head, no clock. This is a Boolean circuit. What is the relationship between these two views?

Gates and first circuits#

A circuit is built from two kinds of gates. An AND gate outputs one when its inputs are all one. An OR gate outputs one when any input is one. You can negate any wire, flipping its value; negation is free and does not count as a gate. Every Boolean function can be built from these.

Exclusive-or outputs one when exactly one of its two inputs is one. One AND gate checks $x$ and not $y$, another checks not $x$ and $y$, and an OR combines them. Three gates. Set $x$ to one and $y$ to zero, let the values propagate, and the output is one. Set both to one and the output is zero.

Pause and try: build majority on three inputs.

Majority outputs one when at least two of the three inputs are one. Notice that "at least two are one" means some pair is all ones. So take three AND gates, one for each pair: $a$ and $b$, $a$ and $c$, $b$ and $c$. Feed all three into a single OR. Four gates in total. Check it: on input $a=1,b=1,c=0$ the first AND fires and the output is one; on $a=0,b=0,c=1$ no pair fires and the output is zero.

A circuit has a fixed number of input wires. The XOR circuit handles two inputs; three inputs need a different, larger circuit. To handle a problem on all input lengths you need a circuit family: one circuit $C_n$ for each $n$. How do these families relate to Turing machines?

Compiling algorithms into circuits#

Take a Turing machine that runs in polynomial time on inputs of length $n$. At each step it reads a cell, updates its state, and moves the head. The head movement depends on the input, so you cannot wire a fixed circuit to follow it directly. First transform the machine into an oblivious one, where the head pattern depends only on the input length (a good exercise). Now you can unroll the computation into a circuit: each layer of gates computes the next configuration from the previous one. Polynomial time becomes polynomial size. Any efficient algorithm compiles into a circuit family.

The connection runs the other way too. Given a circuit and an input, a Turing machine can evaluate it in polynomial time, resolving each gate in order from inputs to output. In fact circuit evaluation is P-complete: just as every problem in NP reduces to SAT, every polynomial-time computation reduces to evaluating a circuit. The two models can encode each other.

Circuits can decide the halting problem#

So circuits and algorithms are tightly connected. But a circuit family can decide the halting problem, something no Turing machine can do.

For each input length $n$ there are only finitely many Turing machine descriptions of length $n$. Each one either halts or doesn't: a finite table of answers. A circuit that hardcodes those answers exists, and the family decides halting one input length at a time.

No algorithm produces these circuits. They exist as mathematical objects, encoding information no procedure can generate. This is what non-uniform means. The families we compiled from algorithms were uniform: an algorithm produced the $n$-th circuit from $n$. Non-uniform families have no such constraint, and they can contain arbitrary knowledge about each input length.

Size, and Shannon's counting argument#

Unconstrained circuit families are too powerful, so the natural response is to measure the number of gates. Circuit size is the analog of time complexity.

There are $2^{2^n}$ Boolean functions on $n$ inputs, but far fewer small circuits. In 1949 Shannon proved by counting that most functions require on the order of $2^n/n$ gates. In 1958 Lupanov proved a matching upper bound: every function can be computed with roughly $2^n/n$ gates. The bounds match, making them tight. Most Boolean functions genuinely need exponentially many gates.

Depth and parallelism#

Size counts total gates. Depth counts the longest path from input to output, the number of sequential steps if you evaluate gates in parallel.

NC restricts to bounded fan-in, where each gate reads two inputs. AC allows unbounded fan-in, where a single gate can read any number of inputs. The superscript is the power of the logarithm in the depth bound: $N{C}^i$ and $A{C}^i$ have depth $O\left({\log }^{i}n\right)$. An unbounded fan-in AND on $n$ inputs is just a balanced tree of two-input ANDs with logarithmic depth, so the tree adds one log factor and $A{C}^i$ is contained in $N{C}^{i+1}$. The classes interleave: $N{C}^0$, $A{C}^0$, $N{C}^1$, $A{C}^1$, and so on. Take the union and NC equals AC. Uniform NC sits inside P, and whether P equals NC is still open.

Parity needs depth#

Separations at the bottom of the hierarchy are known. Parity, whether the number of ones in the input is odd, cannot be computed by constant-depth polynomial-size circuits, even with unbounded fan-in.

The argument uses sensitivity. The sensitivity of a function at an input is the number of input bits you can flip to change the output. Parity has maximum sensitivity: flipping any single bit changes the output, so every bit matters equally and the average sensitivity is $n$.

A constant-depth circuit of bounded size cannot have that property. Each gate combines its inputs, and with only a constant number of layers, most input bits can influence the output only through a bottleneck. The average sensitivity of any $A{C}^0$ function on $n$ inputs is at most polylogarithmic in $n$. But parity's is $n$. For large enough inputs, no constant-depth circuit can match it. Parity is not in $A{C}^0$: one of the few unconditional lower bounds we have.

P/poly, and circuits for coin flips#

A problem is in P/poly if a polynomial-size circuit family decides it. Every problem in P is in P/poly; that is the compilation argument from earlier. But P/poly is strictly larger. Encode the number of a Turing machine as the length of the input: for each $n$, the circuit outputs a fixed bit, namely whether machine $n$ halts. Even constant-size circuits can compute undecidable problems. Non-uniform complexity captures a different structural notion of difficulty, despite compiling to and from uniform computation.

Circuits also absorb randomness. A probabilistic Turing machine flips coins as it runs and may answer differently on different runs. BPP is the class of problems decidable by a polynomial-time probabilistic machine that is right on every input with probability at least two thirds. Adleman proved BPP is contained in P/poly. Fix an input length $n$. Amplify by repeating the computation and taking the majority, so each input fails on fewer than a $1/2^n$ fraction of coin sequences. There are only $2^n$ inputs, so by a union bound some single sequence works for all of them. Hardwire that sequence into the circuit.

Adleman removed the randomness, but only non-uniformly, with a different fix for each input length. Can a single algorithm do it? Does BPP equal P? Most complexity theorists believe it does: every efficient randomized algorithm should have an efficient deterministic counterpart. The field of derandomization studies exactly this. The core idea is that a sequence that looks random to any small circuit can substitute for real randomness, and constructing such sequences turns out to be deeply connected to circuit lower bounds, the very topic of this video.

If you remember three things#

1. Circuits are computation as structure: size corresponds to sequential time, depth to parallel time, and polynomial-time algorithms compile into polynomial-size circuit families.
2. Non-uniformity is real power. Circuit families can hardcode answers no algorithm can produce, including the halting problem, which is why we measure them by size.
3. Shannon's counting shows most functions need exponentially many gates, yet the only unconditional separations we can prove sit at the bottom of the hierarchy, like parity outside $A{C}^0$.