Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 59 / 3 / d

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(\mathrm{mod}3)$,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