We show that the product of $n$ $3 \times 3$ matrices of $n$-bit integers
can be computed in $P$-uniform $FNC^1$. Since this problem is
complete~\cite{BOC:const_registers} for formul\ae\ in
$\{+, \cdot\}$ on $n$-bit integers, we conclude that ``algebraic $NC^1$''
on integers is equal to the usual Boolean notion of $NC^1$ functions.
DIMACS Home Page