DIMACS TR: 96-04

An Isomorphism Theorem for Circuit Complexity



Authors: Manindra Agrawal and Eric Allender

ABSTRACT

We show that all sets complete for NC^1 under AC^0 reductions are isomorphic under AC^0-computable isomorphisms.

Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC^1-computable many-one reductions, the sets complete for C under NC^0 reductions are all isomorphic under AC^0-computable isomorphisms. Our result showing that the complete degree for NC^1 collapses to an isomorphism type follows from a theorem showing that in NC^1, the complete degrees for AC^0 and NC^0 reducibility coincide. This 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.

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


DIMACS Home Page