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

Authors: Agrawal M.1; Allender E.2; Rudich S.3

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

Publisher: Academic Press

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

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

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$54.13 plus tax

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A