Cover Image

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grüne, Christoph, Johannes, Berit, Orlin, James B., Wulf, Lasse
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

The Complexity of Stackelberg Pricing Games
by: Grüne, Christoph, et al.
Published: (2025)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
by: Dingel, David, et al.
Published: (2024)

Maker-Maker games of rank 4 are PSPACE-complete
by: Galliot, Florian, et al.
Published: (2025)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
by: Galliot, Florian
Published: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Some conditions implying if P=NP then P=PSPACE
by: Rodriguez, Ismael
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

Battle Sheep is PSPACE-complete
by: Burke, Kyle, et al.
Published: (2025)

Hierarchies of Minion Tests for PCSPs through Tensors
by: Ciardo, Lorenzo, et al.
Published: (2022)

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

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

Factorization norms and Zarankiewicz problems
by: Tomon, István
Published: (2025)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

The geodesic cover problem for butterfly networks
by: Manuel, Paul, et al.
Published: (2022)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

Testing Isomorphism of Graphs in Polynomial Time
by: Xue, Rui
Published: (2023)

Paintbucket on graphs is PSPACE-complete
by: Saunders, Ethan J., et al.
Published: (2024)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

A Simple Sub-Polynomial Degree Coboundary Expander
by: Hopkins, Max, et al.
Published: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)