## DIMACS TR: 97-60

## Reductions in Circuit Complexity: An Isomorphism Theorem and a
Gap Theorem

### Authors: Manindra Agrawal, Eric Allender, and Steven Rudich

**
ABSTRACT
**

We show that all sets that are complete for NP under non-uniform AC^0
reductions are isomorphic under non-uniform AC^0-computable isomorphisms.
Furthermore, these sets remain NP-complete even under non-uniform NC^0
reductions.
More generally, we show two theorems that hold for any complexity
class C closed under (uniform) NC^1-computable many-one reductions.
Gap: The sets that are complete for C under AC^0 and NC^0 reducibility
coincide.
Isomorphism: The sets complete for C under AC^0 reductions are all
isomorphic under isomorphisms computable and invertible
by AC^0 circuits of depth three.
Our Gap Theorem does not hold for strongly uniform
reductions: we show that there are Dlogtime-uniform AC^0-complete
sets for NC^1 that are not Dlogtime-uniform NC^0-complete.}
(This technical report replaces DIMACS TR 96-04.)

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-60.ps.gz

DIMACS Home Page