An isomorphism theorem for circuit complexity

Abstract

We show that all sets complete for NC¹ under AC⁰ reductions are isomorphic under AC⁰-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¹-computable many-one reductions, the sets complete for C under NC⁰ reductions are all isomorphic under AC⁰ -computable isomorphisms. Our result showing that the complete degree for NC¹ collapses to an isomorphism type follows from a theorem showing that in NC¹, the complete degrees for AC⁰ and NC⁰ reducibility coincide. This theorem does not hold for strongly uniform reduction: we show that there are Dlogtime-uniform AC⁰-complete sets for NC¹ that are not Dlogtime-uniform NC⁰-complete.