= Solution
The class <NC1> consists of languages having polynomial-size, bounded-fan-in <Boolean circuit> families of depth $O(\log n)$. Under a uniform convention one requires the wiring to be constructible in <logarithmic space>; the construction below meets that requirement as well as the nonuniform one.
Write a length-$n$ binary input with most significant bit first as $x_1\cdots x_n$. Since $2^m\equiv(-1)^m\pmod3$,
$$
x\equiv\sum_{i=1}^n(-1)^{n-i}x_i\pmod3.
$$
Represent residues zero, one and two by two bits, respectively $00,01,10$. Each input produces residue zero when it is zero; when it is one it produces residue one or two according to the parity of $n-i$. This uses only constants and wires.
A two-residue addition modulo three is a fixed function of four <Boolean variables> and has a constant-size, constant-depth bounded-fan-in <Boolean circuit>. Define its unused $11$ encodings arbitrarily; valid inputs always produce a valid residue encoding. Use a balanced binary tree of these adders, padding with zero residues to a power of two. There are $O(n)$ adders and $O(\log n)$ layers. A final constant-size gate checks that the residue is $00$.
This <balanced finite-monoid reduction circuit> is uniform: leaf signs follow index parity and internal connections follow the indices in the balanced tree, all calculable in <logarithmic space>. Leading zeros cause no difficulty; the empty input can be assigned the zero-integer constant convention. Consequently
$$
\boxed{\mathrm{MOD3}\in\mathrm{NC}^1}.
$$
Back to article page
