Can I read On the NP-Isomorphism Problem with Respect to Random Instances on EtoBox?

On the NP-Isomorphism Problem with Respect to Random Instances by J. Wang; J. Belanger is a Computer Science article available to read on EtoBox.

What is On the NP-Isomorphism Problem with Respect to Random Instances about?

This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomialtime computable and invertible bijections among NP-complete sets that preserve the underlying natural distributions on random instances. We show that there are natural NP-complete problems which are not polynomially isomorphic when instances are chosen at random because no polynomial-time isomorphisms can preserve the underlying natural distributions on instances of these problems. On the other hand, we show that all the known average-case NP-complete problems under many-one reductions are polynomially isomorphic with respect to their distributions on random instances. Simple and accessible proofs to the known average-case NP-complete problems are presented when establishing the isomorphism result. New averagecase NP-complete problems are also presented. (C) 1995 Academic Press, Inc.

Who reads On the NP-Isomorphism Problem with Respect to Random Instances?

Author

J. Wang; J. Belanger

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

1995

Language

EN

Field

Computer Science (Physical Sciences)