97-60: Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem

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