An Oracle with no UP-Complete Sets, but NP=PSPACE

2024/04/29 by Dingel, David, Egidy, Fabian, Glaßer, Christian
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2404.19104

Abstract

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 [HH88] and one by Ogiwara and Hemachandra [OH93]. 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 [Pud17], e.g., the implications UP \Longrightarrow CON^N and SAT \Longrightarrow 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.

Related

• P-Optimal Proof Systems for Each NP-Complete Set but no Complete Disjoint NP-Pairs 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
• P-Optimal Proof Systems for Each coNP-Complete Set and no Complete Problems in NP\capcoNP Relative to an Oracle
• Oracle with P=NP∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
• P\not=NP relative to a P-complete oracle