Oracles for structural properties: The isomorphism problem and public-key cryptography

摘要

There exists an oracle, relative to which, P ≠ NP, and each of the following properties hold: 1.(i)All Σ2P-complete sets are p-isomorphic;2.(ii)P-inseparable pairs of sets in NP do not exist;3.(iii)Intractable public-key cryptosystems do not exist;4.(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.