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

Documenti analoghi

• Optimal Proof Systems for Complex Sets are Hard to Find
  di: Egidy, Fabian, et al.
  Pubblicazione: (2024)
• Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
  di: Mitosek, Piotr
  Pubblicazione: (2024)
• Recursive Jump Operators and Optimal Proof Systems
  di: Egidy, Fabian
  Pubblicazione: (2026)
• The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
  di: Egidy, Fabian
  Pubblicazione: (2026)
• Proofs of NP = coNP = PSPACE: Current upgrade
  di: Gordeev, Lev, et al.
  Pubblicazione: (2023)