Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-002 | 10th January 1996 00:00

An Isomorphism Theorem for Circuit Complexity

RSS-Feed




TR96-002
Authors: Manindra Agrawal, Eric Allender
Publication: 10th January 1996 17:54
Downloads: 2386
Keywords: 


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.



ISSN 1433-8092 | Imprint