Agrawal, M. ; Allender, E. ; Impagliazzo, R. ; Pitassi, T. ; Rudich, S.
(2001)
*Reducing the complexity of reductions*
Computational Complexity, 10
(2).
pp. 117-138.
ISSN 1016-3328

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/bbar426549dv33...

Related URL: http://dx.doi.org/10.1007/s00037-001-8191-1

## 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^{0} reductions are isomorphic under isomorphisms computable and invertible via (non-uniform) depth-three AC^{0} 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^{0} reductions are in fact already complete under NC^{0} reductions. The following questions were left open in that paper: ¶1. Does the "gap" between NC^{0} and AC^{0} extend further? In particular, is every set complete under polynomial-time reducibility already complete under NC^{0} 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^{0} reductions. More precisely, we show that for any class closed under uniform TC^{0}-computable many-one reductions, the following three theorems hold: ¶1. If contains sets that are complete under a notion of reduction at least as strong as Dlogtime-uniform AC^{0}[mod 2] reductions, then there are such sets that are not complete under (even non-uniform) AC^{0} reductions. ¶2. The sets complete for under P-uniform AC^{0} reductions are all isomorphic under isomorphisms computable and invertible by P-uniform AC^{0} circuits of depth-three. ¶3. There are sets complete for under Dlogtime-uniform AC^{0} reductions that are not isomorphic under any isomorphism computed by (even non-uniform) AC^{0} 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.)

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer. |

Keywords: | Isomorphisms; Completeness; Constant-Depth Circuits; Berman-Hartmanis Conjecture; Powering in Finite Fields |

ID Code: | 20221 |

Deposited On: | 20 Nov 2010 14:50 |

Last Modified: | 10 Apr 2012 10:31 |

Repository Staff Only: item control page