Oracle with $\mathrm{P=NP\cap coNP}$, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer · arXiv (Cornell University) · 2022
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.