5 citations · 28 across the 21 of their papers we have counts for
6 papers · 1 filter
Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard
Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
We build a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining…
Cookie Clicker
Erik D. Demaine, Hiro Ito, Stefan Langerman +3
Cookie Clicker is a popular online incremental game where the goal of the game is to generate as many cookies as possible. In the game you start with an initial cookie generation r…
Losing at Checkers is Hard
Jeffrey Bosboom, Spencer Congero, Erik D. Demaine +2
We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers whe…
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…
The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
Kaiying Hou, Jayson Lynch
Finding Hamitonian Cycles in square grid graphs is a well studied and important questions. More recent work has extended these results to triangular and hexagonal grids, as well as…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw…