An isomorphism theorem for circuit complexity

Agrawal, M. ; Allender, E. (1996) An isomorphism theorem for circuit complexity Proceedings of Eleventh Annual IEEE Conference on Computational Complexity . pp. 2-11. ISSN 1093-0159

Full text not available from this repository.

Official URL:

Related URL:


We show that all sets complete for NC1 under AC0 reductions are isomorphic under AC0-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC1-computable many-one reductions, the sets complete for C under NC0 reductions are all isomorphic under AC0 -computable isomorphisms. Our result showing that the complete degree for NC1 collapses to an isomorphism type follows from a theorem showing that in NC1, the complete degrees for AC0 and NC0 reducibility coincide. This theorem does not hold for strongly uniform reduction: we show that there are Dlogtime-uniform AC0-complete sets for NC1 that are not Dlogtime-uniform NC0-complete.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:95349
Deposited On:07 Nov 2012 05:27
Last Modified:07 Nov 2012 05:27

Repository Staff Only: item control page