Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

ISSN 1433-8092 | Imprint