AC0 (${\mathrm{AC}}^0$)

AC0 is the class of decision problems computable by Boolean circuit families with polynomial circuit size, constant circuit depth and unbounded-fan-in AND gates and OR gates, together with NOT gates. The depth bound is independent of input length. Uniform and nonuniform versions must be distinguished; without a qualifier the Circuit family need not be generated by one efficient algorithm.

Conjunction and disjunction of $n$ inputs each take one gate. Testing equality of two $n$-bit strings also has constant depth: test equality at every bit using a fixed small circuit, then AND those results. In contrast, the parity function cannot be computed by constant-depth polynomial-size circuits of this gate basis. Adding an unbounded parity gate changes the model and defeats that conclusion. Counting only depth while ignoring size would also be misleading: a truth-table Disjunctive normal form represents any Boolean function at constant depth but may require exponentially many gates.