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

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