ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > ISOMORPHISMS:
Reports tagged with Isomorphisms:
TR96-002 | 10th January 1996
Manindra Agrawal, Eric Allender

An Isomorphism Theorem for Circuit Complexity

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 ... more >>>



ISSN 1433-8092 | Imprint