14 citations · 14 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2018★ 14 cited
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
Erik D. Demaine, Isaac Grosof, Jayson Lynch +1
We initiate a general theory for analyzing the complexity of motion planning of a single robot through a graph of "gadgets", each with their own state, set of locations, and allowe…
cs.CC2017
Push-Pull Block Puzzles are Hard
Erik D. Demaine, Isaac Grosof, Jayson Lynch
This paper proves that push-pull block puzzles in 3D are PSPACE-complete to solve, and push-pull block puzzles in 2D with thin walls are NP-hard to solve, settling an open question…