There exists an oracle, relative to which P not= NP and each of the following properties hold: (i) all Sigma /sup p//sub 2/-complete sets are p-isomorphic; (ii) P-inseparable pairs of sets in NP do not exist; (iii) intractable public-key cryptosystems do not exist; and (iv) NP-complete sets are closed under union of disjoint sets. Remarkably, these properties all follow from one oracle construction, namely, it is proved that there is an oracle A such that every two disjoint sets in NP/sup A/ are P-separable, and Sigma /sup P//sub 2/= union (DTIME(2/sup p/) mod p is a polynomial). Additional related relativization results are presented.
展开▼
机译：相对于此，P not = NP且具有以下每个特性：（i）所有Sigma / sup p // sub 2 /-完全集都是p同构的; （ii）NP中不存在P不可分的集合对; （iii）不存在棘手的公钥密码系统; （iv）NP不完全集在不交集的并集下被封闭。值得注意的是，这些属性均来自一个预言结构，即证明存在一个预言A，使得NP / sup A /中的每两个不交集都是P可分离的，而Sigma / sup P // sub 2 / =并集（DTIME（2 / sup p /）mod p是一个多项式）。提出了其他相关的相对化结果。
展开▼
