An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916229495652352 |
|---|---|
| author | Dingel, David Egidy, Fabian Glaßer, Christian |
| author_facet | Dingel, David Egidy, Fabian Glaßer, Christian |
| contents | 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ák [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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19104 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$ Dingel, David Egidy, Fabian Glaßer, Christian Computational Complexity 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ák [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. |
| title | An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$ |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.19104 |