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

Manindra Agrawal, Eric Allender, Steven Rudich

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

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 script C sign closed under (uniform) NC1-computable many-one reductions. Gap: The sets that are complete for script C sign under AC0 and NC0 reducibility coincide. Isomorphism: The sets complete for script C sign 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.

Original languageEnglish (US)
Pages (from-to)127-143
Number of pages17
JournalJournal of Computer and System Sciences
Volume57
Issue number2
DOIs
StatePublished - Oct 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem'. Together they form a unique fingerprint.

Cite this