96-23: Integer $NC^1$ is equal to Boolean $NC^1$

DIMACS TR: 96-23

Integer NC^1 is equal to Boolean NC^1

Author: Stephen Bloch

ABSTRACT
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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-23.ps.gz

DIMACS Home Page