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

摘要

We show that all sets that are complete for NP under nonuniformAC0reductions are isomorphic under nonuniformAC0-computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniformNC0reductions. 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 underAC0andNC0reducibility coincide.Isomorphism: The sets complete for C underAC0reductions are all isomorphic under isomorphisms computable and invertible byAC0circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions; we show that there are Dlogtime-uniformAC0-complete sets forNC1that are not Dlogtime-uniformNC0-complete.