scientific article
From MaRDI portal
Publication:3305736
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.
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
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
