2026-07-24T14:56:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20606 2024-08-23T05:50:29Z ddc:004 open_access

An Oracle with no UP-Complete Sets, but NP = PSPACE Dingel, David Egidy, Fabian Glaßer, Christian Computational Complexity Promise Classes Complete Sets Oracle Construction We construct an oracle relative to which NP = PSPACE, but UP has no many-one complete sets. This combines the properties of an oracle by Hartmanis and Hemachandra [J. Hartmanis and L. A. Hemachandra, 1988] and one by Ogiwara and Hemachandra [Ogiwara and Hemachandra, 1991]. The oracle provides new separations of classical conjectures on optimal proof systems and complete sets in promise classes. This answers several questions by Pudlák [P. Pudlák, 2017], e.g., the implications UP ⟹ CON^𝖭 and SAT ⟹ TFNP are false relative to our oracle. Moreover, the oracle demonstrates that, in principle, it is possible that TFNP-complete problems exist, while at the same time SAT has no p-optimal proof systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Dingel and Fabian Egidy and Christian Glaßer 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.50 urn:nbn:de:0030-drops-206063 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.50 eng https://creativecommons.org/licenses/by/4.0/legalcode