Reducing the complexity of reductions

Manindra Agrawal; Eric Allender; Russell Impagliazzo; Toniann Pitassi; Steven Rudich

doi:https://doi.org/10.1007/s00037-001-8191-1

Reducing the complexity of reductions

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

SAS - Computer Science

Rutgers, The State University

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

Abstract

We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC⁰ reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC⁰ circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a "Gap Theorem", showing that all sets complete under AC⁰ reductions are in fact already complete under NC⁰ reductions. The following questions were left open in that paper: 1. Does the "gap" between NC⁰ and AC⁰ extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC⁰ reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under isomorphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman-Hartmanis isomorphism conjecture is true for P-uniform AC⁰ reductions. More precisely, we show that for any class C closed under uniform TC⁰-computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC⁰ [mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC⁰ reductions. 2. The sets complete for C under P-uniform AC⁰ reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC⁰ circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC⁰ reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC⁰ circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.).

Original language	English (US)
Pages (from-to)	117-138
Number of pages	22
Journal	Computational Complexity
Volume	10
Issue number	2
DOIs	https://doi.org/10.1007/s00037-001-8191-1
State	Published - 2001

ASJC Scopus subject areas

Theoretical Computer Science
Mathematics(all)
Computational Theory and Mathematics
Computational Mathematics

Keywords

Berman-Hartmanis conjecture
Completeness
Constant-depth circuits
Isomorphisms
Powering in finite fields

Access to Document

https://doi.org/10.1007/s00037-001-8191-1

Cite this

@article{efd9110903dc48119a673aa38eab725e,

title = "Reducing the complexity of reductions",

abstract = "We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a {"}Gap Theorem{"}, showing that all sets complete under AC0 reductions are in fact already complete under NC0 reductions. The following questions were left open in that paper: 1. Does the {"}gap{"} between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under isomorphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman-Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0-computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 [mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.).",

keywords = "Berman-Hartmanis conjecture, Completeness, Constant-depth circuits, Isomorphisms, Powering in finite fields",

author = "Manindra Agrawal and Eric Allender and Russell Impagliazzo and Toniann Pitassi and Steven Rudich",

note = "Funding Information: Part of the first author{\textquoteright}s research was done while visiting the University of Ulm under an Alexander von Humboldt Fellowship. The research of the second author was supported in part by NSF grants CCR-9509603, CCR-9734918, and CCR-0104823. The research of the third author was supported by NSF Awards CCR-92-570979 and CCR-0098197, by Sloan Research Fellowship BR-3311, and USA-Israel BSF Grant 97-00188. The research of the third author was supported by NSF Award CCR-94-57782, and USA-Israel BSF Grant 95-00238.",

year = "2001",

doi = "https://doi.org/10.1007/s00037-001-8191-1",

language = "English (US)",

volume = "10",

pages = "117--138",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "2",

}

TY - JOUR

T1 - Reducing the complexity of reductions

AU - Agrawal, Manindra

AU - Allender, Eric

AU - Impagliazzo, Russell

AU - Pitassi, Toniann

AU - Rudich, Steven

N1 - Funding Information: Part of the first author’s research was done while visiting the University of Ulm under an Alexander von Humboldt Fellowship. The research of the second author was supported in part by NSF grants CCR-9509603, CCR-9734918, and CCR-0104823. The research of the third author was supported by NSF Awards CCR-92-570979 and CCR-0098197, by Sloan Research Fellowship BR-3311, and USA-Israel BSF Grant 97-00188. The research of the third author was supported by NSF Award CCR-94-57782, and USA-Israel BSF Grant 95-00238.

PY - 2001

Y1 - 2001

N2 - We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a "Gap Theorem", showing that all sets complete under AC0 reductions are in fact already complete under NC0 reductions. The following questions were left open in that paper: 1. Does the "gap" between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under isomorphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman-Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0-computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 [mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.).

AB - We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC0 reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC0 circuits. One of the main tools in proving the isomorphism theorem in Agrawal et al. (1998) is a "Gap Theorem", showing that all sets complete under AC0 reductions are in fact already complete under NC0 reductions. The following questions were left open in that paper: 1. Does the "gap" between NC0 and AC0 extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC0 reductions? 2. Does a uniform version of the isomorphism theorem hold? 3. Is depth-three optimal, or are the complete sets isomorphic under isomorphisms computable by depth-two circuits? We answer all of these questions. In particular, we prove that the Berman-Hartmanis isomorphism conjecture is true for P-uniform AC0 reductions. More precisely, we show that for any class C closed under uniform TC0-computable many-one reductions, the following three theorems hold: 1. If C contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC0 [mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC0 reductions. 2. The sets complete for C under P-uniform AC0 reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC0 circuits of depth-three. 3. There are sets complete for C under Dlogtime-uniform AC0 reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC0 circuits of depth two. To prove the second theorem, we show how to derandomize a version of the switching lemma, which may be of independent interest. (We have recently learned that this result is originally due to Ajtai and Wigderson, but it has not been published.).

KW - Berman-Hartmanis conjecture

KW - Completeness

KW - Constant-depth circuits

KW - Isomorphisms

KW - Powering in finite fields

UR - http://www.scopus.com/inward/record.url?scp=0035568114&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035568114&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/s00037-001-8191-1

DO - https://doi.org/10.1007/s00037-001-8191-1

M3 - Article

VL - 10

SP - 117

EP - 138

JO - Computational Complexity

JF - Computational Complexity

SN - 1016-3328

IS - 2

ER -

Reducing the complexity of reductions

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this