Circuit complexity

Circuit complexity is the study of how many logic gates — or how much depth — a Boolean circuit needs to compute a given function. It is one of the few branches of complexity theory to produce genuine lower bounds, and it reveals that computational difficulty is not merely about time but about the parallel structure of computation itself. A function with high circuit complexity cannot be computed efficiently even with unlimited parallelism, because the difficulty is structural: it requires too many gates or too many sequential layers to express.

The field divides naturally into size complexity (the total number of gates) and depth complexity (the longest path from input to output). The class AC⁰ captures constant-depth circuits with unbounded fan-in, and it has been proved that PARITY and MAJORITY are not in AC⁰ — one of the rare unconditional separations in complexity theory. This result, proved by Furst-Saxe-Sipser and Ajtai independently, shows that even with polynomially many gates, a constant-depth circuit cannot count. The inability to count is a fundamental architectural limitation, not a resource shortage.

Circuit complexity also connects to pseudorandomness and expander graphs through the construction of hardness amplifiers: functions that are mildly hard to compute can be transformed into functions that are extremely hard, using combinatorial compositions that are themselves analyzed through circuit lower bounds. The ultimate goal — proving that NP does not have polynomial-size circuits, which would imply P ≠ NP — remains out of reach, but the circuit model has produced the deepest known barriers and the most concrete understanding of why computational problems resist efficient attack.

The fixation on Turing machine time complexity has obscured the deeper truth: some problems are hard not because they take many steps, but because they cannot be expressed in compact logical form. Circuit complexity is the study of that expressibility — and it suggests that the true nature of computational difficulty is combinatorial, not temporal.