Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dingel, David, Egidy, Fabian, Glaßer, Christian
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Proof Systems for Complex Sets are Hard to Find
von: Egidy, Fabian, et al.
Veröffentlicht: (2024)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
von: Mitosek, Piotr
Veröffentlicht: (2024)

Recursive Jump Operators and Optimal Proof Systems
von: Egidy, Fabian
Veröffentlicht: (2026)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
von: Egidy, Fabian
Veröffentlicht: (2026)

Proofs of NP = coNP = PSPACE: Current upgrade
von: Gordeev, Lev, et al.
Veröffentlicht: (2023)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
von: Grüne, Christoph, et al.
Veröffentlicht: (2026)

Some conditions implying if P=NP then P=PSPACE
von: Rodriguez, Ismael
Veröffentlicht: (2026)

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Limit on the computational power of $\mathrm{C}$-random strings
von: Milovanov, Alexey
Veröffentlicht: (2026)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
von: Nye, Logan
Veröffentlicht: (2025)

On Kernelization with Access to NP-Oracles
von: Molter, Hendrik, et al.
Veröffentlicht: (2025)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
von: Chavrimootoo, Michael C., et al.
Veröffentlicht: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Wataridori is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2026)

Nondango is NP-Complete
von: Ruangwises, Suthee
Veröffentlicht: (2023)

A Simple Proof that Ricochet Robots is PSPACE-Complete
von: Balanza-Martinez, Jose, et al.
Veröffentlicht: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
von: MIT Hardness Group, et al.
Veröffentlicht: (2025)

NP-Completeness of Neighborhood Balanced Colorings
von: Asaeedi, Saeed
Veröffentlicht: (2024)

The 2-Attractor Problem is NP-Complete
von: Fuchs, Janosch, et al.
Veröffentlicht: (2023)

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
von: Kothari, Robin, et al.
Veröffentlicht: (2025)

NP-Completeness of Multicast Beamforming in Wireless Communication
von: Shrestha, Sagar
Veröffentlicht: (2025)

Quoridor is PSPACE-Complete
von: Drop, Marius, et al.
Veröffentlicht: (2026)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
von: Digulescu, Mircea-Adrian
Veröffentlicht: (2026)

Atropos-k is PSPACE-complete
von: Yang, Chao, et al.
Veröffentlicht: (2024)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
von: Ruangwises, Suthee
Veröffentlicht: (2024)

New local characterizations of the weighted energy class $\mathcal{E}_{χ,\mathrm{loc}}(Ω)$
von: Quy, Hoang Nhat
Veröffentlicht: (2026)

Recognizing Sumsets is NP-Complete
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
von: DeStefano, Zachary, et al.
Veröffentlicht: (2025)

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam
von: Otsuji, Taisei, et al.
Veröffentlicht: (2026)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
von: Kiatchaipipat, Nattapol, et al.
Veröffentlicht: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

P=NP
von: Deng, Zikang
Veröffentlicht: (2024)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
von: Minevich, Igor, et al.
Veröffentlicht: (2024)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
von: Ani, Hayashi, et al.
Veröffentlicht: (2024)

Maker-Maker games of rank 4 are PSPACE-complete
von: Galliot, Florian, et al.
Veröffentlicht: (2025)

P vs. NP
von: Uribe, Daniel
Veröffentlicht: (2016)

On P Versus NP
von: Gordeev, Lev
Veröffentlicht: (2020)

Estimates of automorphic forms on $\mathrm{SU}(n,1)$
von: Aryasomayajula, Anilatmaja, et al.
Veröffentlicht: (2024)