Isomorphisms, separability, and one-way functions
John D. Rogers · 1995
We present two sets of results in relativized computational complexity theory. Both are concerned with classes of languages contained in NP and both make use of new types of generic oracles. The first set of results involves the following five propositions: (P1) P = NP; (P2) P = UP; (P3) P = NP $\cap$ coNP (P4) All disjoint pairs of NP sets are P-separable; (P5) All disjoint pairs of coNP sets are P-separable. It is relatively easy to show that (P1) implies the rest and that (P4) and (P5) each imply (P3). Grollmann and Selman showed that (P4) implies (P2). Our result is that these are the only implications to hold in every relativized world. The second set of results involves the relationship between the existence of one-way functions and the following conjecture made by Berman and Hartmanis about the structure of the class of NP-complete languages: The Isomorphism Conjecture (IC). Every NP-complete language is isomorphic to SAT. From previous results, we know that there are relativized worlds where: (1) The IC does not hold and one-way functions exist (Kurtz, Mahaney, and Royer); (2) The IC does not hold and one-way functions do not exist (Hartmanis and Hemachandra); (3) The IC holds and one-way functions do not exist (Fenner, Fortnow, and Kurtz). Our main result is that there is a relativized world where the IC holds and one-way functions exist.