An Oracle with no $\mathrmUP$-Complete Sets, but $\mathrmNP=\mathrmPSPACE$
<|reference_start|>An Oracle with no $\mathrmUP$-Complete Sets, but $\mathrmNP=\mathrmPSPACE$: We construct an oracle relative to which $\mathrm{NP} = \mathrm{PSPACE}$, but $\mathrm{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\'ak [Pud17], e.g., the implications $\mathsf{UP} \Longrightarrow \mathsf{CON}^{\mathsf{N}}$ and $\mathsf{SAT} \Longrightarrow \mathsf{TFNP}$ are false relative to our oracle.   Moreover, the oracle demonstrates that, in principle, it is possible that $\mathrm{TFNP}$-complete problems exist, while at the same time $\mathrm{SAT}$ has no p-optimal proof systems.<|reference_end|>
@article{dingel2024an,
    title={An Oracle with no $\mathrm{UP}$-Complete Sets, but
  $\mathrm{NP}=\mathrm{PSPACE}$},
    author={David Dingel, Fabian Egidy, Christian Gla{ss}er},
    journal={arXiv preprint arXiv:2404.19104},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.19104},
    primaryClass={cs.CC}
}