论文标题
带有$ \ mathrm {p = np \ cap conp} $的甲骨文
Oracle with $\mathrm{P=NP\cap coNP}$, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
论文作者
论文摘要
我们构造了一个oracle，$ \ mathrm {p} = \ mathrm {np} \ cap \ mathrm {conp} $，但是在$ \ mathrm {up} $中没有很多完整的集合$ \ mathrm {conp} $ - 对。这有助于Pudlák[Pud17]发起的研究计划，该计划研究了有限域中的不完整，并提到了诸如开放问题之类的牙齿的构建。 Oracle表明$ \ Mathsf {np} \ Cap \ Mathsf {Conp} $在Pudlák研究的假设列表中是必不可少的。因此，应该考虑更强有力的假设，以找到普遍的假设。
We construct an oracle relative to which $\mathrm{P} = \mathrm{NP} \cap \mathrm{coNP}$, but there are no many-one complete sets in $\mathrm{UP}$, no many-one complete disjoint $\mathrm{NP}$-pairs, and no many-one complete disjoint $\mathrm{coNP}$-pairs. This contributes to a research program initiated by Pudlák [Pud17], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that $\mathsf{NP}\cap\mathsf{coNP}$ is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.
