scientific article

DOI10.4230/LIPICS.FUN.2018.18zbMath1489.68105arXiv1806.03539MaRDI QIDQ3305736

Mikhail Rudoy, Jayson Lynch, Erik D. Demaine, Isaac Grosof

Publication date: 11 August 2020

Full work available at URL: https://arxiv.org/abs/1806.03539

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

puzzlesmotion planninghardnessPSPACEZelda

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Artificial intelligence for robotics (68T40)

Related Items (7)

Traversability, reconfiguration, and reachability in the gadget framework ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unnamed Item ⋮ Recursed Is Not Recursive: A Jarring Result ⋮ Traversability, reconfiguration, and reachability in the gadget framework ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ PSPACE-completeness of reversible deterministic systems

Cites Work

• Unnamed Item
• Unnamed Item
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• How to draw a planar graph on a grid
• Pushing blocks is hard.
• Classic Nintendo games are (computationally) hard
• Relationships between nondeterministic and deterministic tape complexities
• Super Mario Bros. Is Harder/Easier than We Thought
• Push-Pull Block Puzzles are Hard
• The complexity of satisfiability problems

This page was built for publication: