AC0

AC0 is the complexity class of decision problems solvable by constant-depth, polynomial-size circuits composed of unbounded fan-in AND and OR gates, plus NOT gates. It is the simplest nontrivial class in the circuit hierarchy — so simple that it cannot even compute the parity function, which asks whether an n-bit input contains an even number of 1s.

This failure is not a quirk but a structural boundary. The landmark result, proved independently by Furst, Saxe, and Sipser and by Miklós Ajtai, uses entirely different methods — probabilistic restriction and finite model theory respectively — yet converges on the same conclusion. AC0 is too shallow to count modulo 2. This makes AC0 the canonical example of a complexity class whose limitations are provable, not merely conjectured, and the parity lower bound remains one of the most robust results in all of circuit complexity.

The fact that AC0 cannot compute parity is often presented as a triumph of complexity theory. It is better understood as a warning: if the simplest hard problem requires two completely unrelated mathematical disciplines to defeat the simplest circuit model, what hope is there for proving strong lower bounds against models only slightly more powerful? AC0 is a beachhead, not a conquest.