aC0

AC0 is a class in circuit complexity consisting of families of boolean circuits that have constant depth, polynomial size, and unbounded fan-in AND and OR gates, with NOT gates allowed only at the inputs. For each input length n there is a circuit Cn that decides the corresponding n-bit input. In many presentations AC0 is treated as a non-uniform class (a different circuit is allowed for each n), though uniform variants exist where a single algorithm generates the circuits.

As a consequence of its constant depth, AC0 circuits can compute simple, highly parallelizable functions efficiently, but they are limited in their counting and global-comstructure capabilities. The class is contained in NC1 and in P/poly, and AC0 is known to be strictly weaker than NC1 since some functions like parity are not in AC0 but lie in NC1. A central result highlighting this limitation is Håstad’s switching lemma, which shows that parity cannot be computed by any polynomial-size AC0 circuit of constant depth. More generally, parity requires superpolynomial size for fixed-depth AC0 circuits, illustrating a fundamental separation between AC0 and deeper circuit classes.

Variants and extensions include AC0[MOD m], which augments AC0 with modulus gates that output 1 when the number of true inputs meets a congruence condition modulo m. For fixed m, AC0[MOD m] has greater computational power than AC0, and parity corresponds to a special case with MOD 2 gates. AC0 provides a baseline for understanding the limits of shallow, parallel computation and the gap to more powerful circuit classes.