Oracle with P=NP∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP

2022/03/21 by Ehrmanntraut, Anton, Egidy, Fabian, Glaßer, Christian
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2203.11079

Abstract

We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint 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 NP\capcoNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.

Related

• An Oracle with no UP-Complete Sets, but NP=PSPACE
• P-Optimal Proof Systems for Each NP-Complete Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• P-Optimal Proof Systems for Each coNP-Complete Set and no Complete Problems in NP\capcoNP Relative to an Oracle
• \P\≠\NP and All Non-Empty Sets in\n \NP\∪\coNP Have P-Optimal Proof Systems Relative to an\n Oracle
• Complete Disjoint coNP-Pairs but no Complete Total Polynomial Search Problems Relative to an Oracle