ON THE NP-ISOMORPHISM PROBLEM WITH RESPECT TO RANDOM INSTANCES

This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomial-time comput able and invertible bijections among NP-complete sets that preserve th e underlying natural distributions on random instances. We show that t here are natural NP-complete problems which are not polynomially isomo rphic when instances are chosen at random because no polynomial-time i somorphisms can preserve the underlying natural distributions on insta nces of these problems, On the other hand, we show that all the known average-case NP-complete problems under many-one reductions are polyno mially isomorphic with respect to their distributions on random instan ces. Simple and accessible proofs to the known average-case NP-complet e problems are presented when establishing the isomorphism result. New average-case NP-complete problems are also presented. (C) 1995 Academ ic Press, Inc.