|
Abstract : |
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, |
