Boolean Circuits

Boolean circuits are the foundational model of computation in computational complexity theory, providing a concrete, non-uniform model of how computational problems are solved by physical hardware. A Boolean circuit is a directed acyclic graph in which input nodes represent problem variables (taking values 0 or 1), output nodes represent the answer, and internal nodes (called gates) compute Boolean functions — typically AND, OR, and NOT — on their incoming edges. The size of a circuit is the number of gates; the depth is the longest path from input to output. These two parameters — size and depth — are the central measures of computational complexity in the circuit model.

Unlike the Turing machine, which is a uniform model (one machine handles all input sizes), Boolean circuits are non-uniform: for each input length n, there may be a different circuit Cₙ. This non-uniformity makes the circuit model both more powerful and more realistic. It is more powerful because a non-uniform family of circuits can solve problems that are uncomputable by Turing machines (a circuit for each input length can encode an arbitrary function). It is more realistic because actual computer hardware is non-uniform: the chip in your phone is designed for a specific word length and does not "scale" to arbitrary input sizes.

The circuit model is the primary framework for proving lower bounds — results showing that certain problems cannot be solved by circuits of restricted size or depth. Despite decades of effort, superpolynomial lower bounds for general circuits remain among the most important open problems in theoretical computer science. The current frontier is barely ahead of where it was in the 1980s: we can prove that certain problems require exponential size for circuits of depth 2 (DNF formulas), and we can prove superpolynomial lower bounds for depth-3 and depth-4 circuits with restricted gate types, but we cannot prove that P ≠ NP by showing that an NP-complete problem requires superpolynomial circuit size.

Circuit Complexity Classes

The main complexity classes in the circuit model are:

• AC⁰: Constant-depth, polynomial-size circuits with AND, OR, and NOT gates of unbounded fan-in. AC⁰ captures highly parallel computation: problems solvable in constant time with polynomially many processors. The canonical result is that parity (determining whether the number of 1s in the input is even) is not in AC⁰ — proved independently by Furst-Saxe-Sipser and Ajtai in 1983. This was the first superpolynomial lower bound for a natural problem and remains one of the most influential results in complexity theory.

• NC: Problems solvable by logarithmic-depth, polynomial-size circuits with bounded fan-in. NC captures efficiently parallelizable problems. The question of whether P = NC is open; it is widely believed that some polynomial-time problems are inherently sequential and cannot be parallelized efficiently.

• P/poly: Problems solvable by polynomial-size circuits (no depth restriction). P/poly contains P and is believed to be strictly larger, but proving this would separate P from NP. The circuit model transforms the P vs NP question into a concrete combinatorial problem: show that some problem in NP requires circuits of superpolynomial size.

• TC⁰: Constant-depth circuits with threshold gates (gates that output 1 if a weighted sum of inputs exceeds a threshold). TC⁰ is believed to be strictly larger than AC⁰, but proving that inner product mod 2 is not in TC⁰ remains open. The class captures more realistic models of neural computation than AC⁰, as threshold gates approximate biological neurons.

The Systems-Theoretic Reading

Boolean circuits encode a systems principle: computation is the propagation of constrained information through a network of simple processing elements. The circuit model strips computation to its essence: variables enter at the bottom, flow through gates that perform local Boolean operations, and emerge as outputs at the top. The global computation is entirely determined by the local gate functions and the wiring pattern. There is no central controller, no global state, no side effects — only the structured flow of information.

This makes the circuit model the natural framework for understanding neural networks as computational devices. A feedforward neural network is, formally, a circuit with threshold (or sigmoid, or ReLU) gates. The depth of the network is the circuit depth; the width is the circuit size. The expressive power of depth — the fact that deep networks can compute functions that shallow networks cannot without exponential size — is precisely the circuit complexity question of whether constant-depth threshold circuits (TC⁰) are strictly contained in depth-d threshold circuits for some d. The field's empirical discovery that "deep learning works" is, from the circuit complexity perspective, the empirical confirmation of a separation that complexity theory has been trying to prove for decades.

The circuit model also illuminates the physical realizability of computation. A Turing machine is an abstract mathematical object; a Boolean circuit is a wiring diagram. Every gate can be implemented by a handful of transistors; every wire by a metal trace. The circuit model asks not "what is computable in principle?" but "what is computable with a given amount of silicon, a given number of clock cycles, and a given energy budget?" These are the questions that matter for actual systems.

Natural Proofs and the Barrier to Lower Bounds

The most significant meta-result in circuit complexity is the natural proofs barrier, identified by Razborov and Rudich in 1994. A "natural" proof of a circuit lower bound is one that defines a property of Boolean functions that is (1) useful (functions with the property are hard for small circuits), (2) constructive (the property can be tested in polynomial time), and (3) large (many random functions have the property). Razborov and Rudich showed that if such a property exists, it can be used to break pseudorandom generators, which implies that P = NP under standard cryptographic assumptions.

The natural proofs barrier means that the techniques that have succeeded for proving small lower bounds — random restrictions, polynomial approximations, communication complexity — cannot be extended to prove the superpolynomial lower bounds needed for P ≠ NP, unless widely believed cryptographic conjectures are false. The barrier has shaped the field's research agenda for three decades, directing attention toward unnatural proof techniques, algebraic methods, and geometric complexity theory — approaches that circumvent the barrier by violating one of its three conditions.

The systems reading of the natural proofs barrier is that the difficulty of proving lower bounds is itself a structural property of the space of computational problems. The barrier does not say that P ≠ NP is unprovable; it says that certain kinds of proofs cannot work. This is analogous to the undecidability of the halting problem: not a limitation of human ingenuity but a mathematical fact about the structure of the object being studied.

Boolean circuit complexity is the most honest branch of theoretical computer science. It does not hide its failures behind asymptotic notation or oracle separations. It confronts directly the question of how much hardware is required to solve a problem, and it admits that for the most important question — whether NP requires superpolynomial circuits — it has nothing to say. This honesty is rare. The field's inability to prove strong lower bounds is not a sign of immaturity but a sign that the problem is genuinely hard, possibly beyond current mathematical techniques. The circuit model is not a solved subject. It is a frontier, and the researchers working on it are climbing a mountain whose peak is not visible.