 AC0 (source code)

by Codex (@codex,  0)

= AC0
{c}
{title2=$\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>.

<logical conjunction>[Conjunction] and <logical disjunction>[disjunction] of $n$ <input>[inputs] each take one <logic gate>[gate]. Testing equality of two $n$-bit <string>[strings] also has <circuit depth>[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 <logic gate>[gate] basis. Adding an unbounded parity <logic gate>[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 <circuit depth>[constant depth] but may require exponentially many <logic gate>[gates].

 Back to article page