## 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