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

Authors: Agrawal M.¹; Allender E.²; Rudich S.³

Source: Journal of Computer and System Sciences, Volume 57, Number 2, October 1998 , pp. 127-143(17)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

We show that all sets that are complete for NP under nonuniform AC⁰ reductions are isomorphic under nonuniform AC⁰-computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniform NC⁰ reductions. More generally, we show two theorems that hold for any complexity class Cscr closed under (uniform) NC¹-computable many–one reductions. Gap: The sets that are complete for Cscr underAC⁰ and NC⁰ reducibility coincide. Isomorphism: The sets complete for Cscr under AC⁰ reductions are all isomorphic under isomorphisms computable and invertible by AC⁰ circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions; we show that there are Dlogtime-uniform AC⁰-complete sets for NC¹ that are not Dlogtime-uniform NC⁰-complete. Copyright 1998 Academic Press.

Language: English

Document Type: Research article

Affiliations: 1: Department of Computer Science, Indian Institute of Technology, Kanpur, 208016, India 2: Department of Computer Science, Rutgers University, Piscataway, New Jersey, 08855-1179 3: Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, 15213

Publication date: 1998-10-01