DIMACS TR: 97-60
Reductions in Circuit Complexity: An Isomorphism Theorem and a
Authors: Manindra Agrawal, Eric Allender, and Steven Rudich
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
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
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:
DIMACS Home Page