Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles

Relationships between NP-sets, Co-NP-sets, and P-sets relative to random oracles
复制标题

NP 集、Co-NP 集和 P 集之间相对于随机预言的关系

DOI：
10.1109/sct.1993.336533
复制
发表时间：
1993
期刊：
[1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference
影响因子：
--
通讯作者：
N.K. Vereschchagin
N.K. Vereschchagin
中科院分区：
--
文献类型：
--
作者：
N.K. Vereschchagin

文献摘要

被引文献

相似文献

证明了相对于随机预言机A（关于统一措施）下列主张成立：（1）存在一对不相交的NP/sup A/-集，它们不可被任何P/sup A/-集分开，（2）存在一对不相交的Co-NP/sup A/-集，它们不可被任何P/sup A/-集分开，（3）存在一个无限Co-NP/supA/-集，不存在无限NP/supA/-子集. &lt;<ETX>&gt;
It is proved that relative to random oracle A (with respect to the uniform measure) the following assertions hold: (1) there is a pair of disjoint NP/sup A/-sets that are separable by no P/sup A/-set, (2) there is a pair of disjoint Co-NP/sup A/-sets that are separable by no P/sup A/-set, and (3) there is an infinite Co-NP/sup A/-set having no infinite NP/sup A/-subset.<<ETX>>