An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$

David Dingel, Fabian Egidy, Christian Glaßer

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 an…