2026-08-06T04:24:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16843 2024-03-06T10:58:28Z ddc:004 open_access

Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP Ehrmanntraut, Anton Egidy, Fabian Glaßer, Christian computational complexity promise classes proof complexity complete sets oracle construction 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 [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anton Ehrmanntraut and Fabian Egidy and Christian Glaßer 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.45 urn:nbn:de:0030-drops-168435 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45 eng https://creativecommons.org/licenses/by/4.0/legalcode