Oracle with $\mathrm{P}=\mathrm{NP}\cap \mathrm{coNP}$, but no Many-One Completeness in UP, DisjNP, and DisjCoNP

Abstract

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.