6 citations · 8 across the 5 of their papers we have counts for
3 papers · 1 filter
Complexity of Solo Chess with Unlimited Moves
Josh Brunner, Lily Chung, Michael Coulombe +3
We analyze Solo Chess puzzles, where the input is an board containing some standard Chess pieces of the same color, and the goal is to make a sequence of capture moves…
PSPACE-Completeness of Reversible Deterministic Systems
Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson +1
We prove PSPACE-completeness of several reversible, fully deterministic systems. At the core, we develop a framework for such proofs (building on a result of Tsukiji and Hagiwara a…
The Computational Complexity of Portal and Other 3D Video Games
Erik D. Demaine, Joshua Lockhart, Jayson Lynch
We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or…