Chicago Journal of Theoretical Computer Science

Volume 1999

Article 2

Published by MIT Press. Copyright 1999 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe.

Randomized Reductions and Isomorphisms

Jie Wang (The University of North Carolina at Greensboro)
24 February 1999
Abstract

Randomizing reductions have provided new techniques for tackling average-case complexity problems. For example, although some NP-complete problems with uniform distributions on instances cannot be complete under deterministic one-one reductions [Wang and Belanger], they are complete under randomized reductions [Venkatesan and Levin]. We study randomized reductions in this paper on reductions that are one-one and honest mappings over certain input domains. These are reasonable assumptions since all the randomized reductions in the literature that are used in proving average-case completeness results possess this property. We consider whether randomized reductions can be inverted efficiently. This gives rise to the issue of randomized isomorphisms. By generalizing the notion of isomorphisms under deterministic reductions, we define what it means for two distributional problems to be isomorphic under randomized reductions. We then show a randomized version of the Cantor-Bernstein-Myhill theorem, which provides a sufficient condition for two distributional problems to be isomorphic under randomized reductions. Based on that condition we show that all the known average-case NP-complete problems (including those that are complete under deterministic reductions) are indeed isomorphic to each other under randomized reductions.


DOI: 10.4086/cjtcs.1999.002
[] Article 1 [] Article 3
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Fri Mar 19 16:02:46 CST 1999