REDUCTIONS IN CIRCUIT COMPLEXITY - AN ISOMORPHISM THEOREM AND A GAP THEOREM

We show that all sets that are complete for NP under nonuniform AC(0) reductions are isomorphic under nonuniform AC(0)-computable isomorphis ms. Furthermore, these sets remain NP-complete even under nonuniform N C0 reductions. More generally, we show two theorems that hold for any complexity class C closed under (uniform) NC1-computable many-one redu ctions. Gap: The sets that are complete for C under AC(0) and NC0 redu cibility coincide. Isomorphism: The sets complete for C under AC(0) re ductions are all isomorphic under isomorphisms computable and invertib le 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 NC1 that are not Dlogtime-uniform NC0-complete . (C) 1998 Academic Press.