research
∙
03/31/2022
The Legend of Zelda: The Complexity of Mechanics
We analyze some of the many game mechanics available to Link in the clas...
share
research
∙
11/23/2020
Arithmetic Expression Construction
When can n given numbers be combined using arithmetic operators from a g...
research
∙
06/01/2020
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
research
∙
03/18/2020
Tatamibari is NP-complete
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an ...
research
∙
02/10/2020
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
We analyze the computational complexity of several new variants of edge-...
research
∙
06/14/2018
Losing at Checkers is Hard
We prove computational intractability of variants of checkers: (1) decid...
research
∙
04/26/2018
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
We analyze the computational complexity of the many types of pencil-and-...
research
∙
03/09/2018
Computational Complexity of Generalized Push Fight
We analyze the computational complexity of optimally playing the two-pla...
research
∙
03/03/2018
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column information--or ...
research
∙
10/14/2017