Buchumschlag

PSPACE-Hard 2D Super Mario Games: Thirteen Doors

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	MIT Hardness Group, Ani, Hayashi, Demaine, Erik D., Hall, Holden, Korman, Matias
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

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Tetris with Few Piece Types
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
von: MIT Gadgets Group, et al.
Veröffentlicht: (2020)

Tetris is Hard with Just One Piece Type
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

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

Complexity of 2D Snake Cube Puzzles
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
von: MIT Hardness Group, et al.
Veröffentlicht: (2026)

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

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

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)

Hive is PSPACE-Hard
von: Andel, Daniël, et al.
Veröffentlicht: (2025)

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

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

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

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
von: Dingel, David, 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)

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

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

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

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

Graph Threading with Turn Costs
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

Verifying Quantized Graph Neural Networks is PSPACE-complete
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
von: Galliot, Florian
Veröffentlicht: (2025)

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

Friends-and-strangers is PSPACE-complete
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Battle Sheep is PSPACE-complete
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Are Depth-2 Regular Expressions Hard to Intersect?
von: Ascone, Rocco, et al.
Veröffentlicht: (2025)

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

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
von: Martinsson, Björn
Veröffentlicht: (2024)

Hardness of SetCover Reoptimization
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

On the Hardness of the Drone Delivery Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2025)

Paintbucket on graphs is PSPACE-complete
von: Saunders, Ethan J., et al.
Veröffentlicht: (2024)

On the Computational Hardness of Quantum One-Wayness
von: Cavalar, Bruno, et al.
Veröffentlicht: (2023)

Hardness Amplification via Group Theory
von: Nareddy, Tejas, et al.
Veröffentlicht: (2024)

Bounds for Hardness Condensation in the Query Model
von: Kayal, Chandrima, et al.
Veröffentlicht: (2026)

Hardness of clique approximation for monotone circuits
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2025)

Computational Complexity of Game Boy Games
von: Tirmazi, Hayder, et al.
Veröffentlicht: (2024)