Oracles for structural properties: The isomorphism problem and public-key cryptography
Steven Thomas Homer, Alan L. Selman · Journal of Computer and System Sciences · 1992
There exists an oracle, relative to which, P ≠ NP, and each of the following properties hold: (i)All Σ2P-complete sets are p-isomorphic; (ii)P-inseparable pairs of sets in NP do not exist; (iii)Intractable public-key cryptosystems do not exist; (iv)NP-complete sets are closed under union of disjoint sets. Remarkably, these properties all follow from one oracle construction. Namely, we prove that there is an oracle A such that every two disjoint sets in NPA are P-separable, and Σ2P = U DTIME(2P)| p is a polynomial. Additional related relativization results are presented also.