Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.

We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0 -computable isomorphisms. Furthermore, these sets remain NP-complete even under non-uniform NC 0 reductions. More generally, we show two theorems that hold for any complexity class C closed under (uniform) NC 1 -computable many-one reductions. Gap: The sets that are complete for C under AC 0 and NC 0 reducibility coincide. Isomorphism: The sets complete for C under AC 0 reductions are all isomorphic under isomorphisms computable and invertible by AC 0 circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions: we show that there are Dlogtime-uniform AC 0 -complete sets for NC 1 that are not Dlogtime-uniform NC 0 - complete. 1 Introduction The notion of complete sets in complexity classes provides one of the most useful tools currently available for classifying the complexity of computational problems. Since the mid-19..