NC1 (${\mathrm{NC}}^1$)

Languages computable by polynomial-size Boolean circuit families of bounded fan-in and depth $O(\log n)$. One can specify the nonuniform or logspace-uniform convention explicitly. Balanced constant-size operations give examples such as the MOD3 binary divisibility problem without nonuniform advice.

For a binary numeral, its remainder is the sum of its bits weighted alternately by $+1$ and $-1$ from the least significant position. A balanced finite-monoid reduction circuit adds these residues modulo three in two-bit encodings. A final zero test gives a uniform linear-size logarithmic-depth Boolean circuit, proving membership in NC1.

A fixed finite monoid operation has a constant-size Boolean truth-table Boolean circuit on its constant-bit encodings. Reduce $n$ elements in a balanced binary tree to get linear size and logarithmic depth. Associativity ensures that tree grouping does not change the product. MOD3 uses addition in the three-element residue group, with input-position signs handled at the leaves.