Reductions in circuit complexity: an isomorphism theorem and a gap theorem

Abstract

We show that all sets that are complete for NP under nonuniform AC⁰ reductions are isomorphic under nonuniform AC⁰-computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniform NC⁰ reductions. More generally, we show two theorems that hold for any complexity class C closed under (uniform) NC¹-computable many-one reductions.Gap: The sets that are complete for C under AC⁰ and NC⁰ reducibility coincide. Isomorphism: The sets complete for C under AC⁰ reductions are all isomorphic under isomorphisms computable and invertible by AC⁰ circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions; we show that there are Dlogtime-uniform AC⁰-complete sets for NC¹ that are not Dlogtime-uniform NC⁰-complete.