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

✍ Scribed by Manindra Agrawal; Eric Allender; Steven Rudich

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 496 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1583

✦ Synopsis

We show that all sets that are complete for NP under nonuniform AC 0 reductions are isomorphic under nonuniform AC 0 -computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniform 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. ] 1998 Academic Press Isomorphism Theorem. The sets complete for C under AC 0 reductions are all isomorphic under AC 0 -computable isomorphisms.

Gap Theorem. The sets that are complete for C under AC 0 and NC 0 reducibility coincide.

The remainder of the Introduction will present a more detailed description of these theorems and previous related work.

1.1. The Isomorphism Theorem

The Berman Hartmanis conjecture has inspired a great deal of work in complexity theory, and we cannot review Article No.