A door gadget has two states and three tunnels that can be traversed by an agent (player,
robot, etc.): the" open" and" close" tunnel sets the gadget's state to open and closed …

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 …

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 …

This thesis develops a framework for proving computational complexity results about motion
planning problems. The model captures reactive environments with local interaction. We …

The physics-based simulation game Angry Birds has been heavily researched by the AI
community over the past five years, and has been the subject of a popular AI competition …

We analyze some of the many game mechanics available to Link in the classic Legend of
Zelda series of video games. In each case, we prove that the generalized game with that …

This paper presents several proofs for the computational complexity of the popular physics-
based puzzle game AngryBirds. By using a combination of different gadgets within this …

We analyze some of the many game mechanics available to Link in the classic Legend of
Zelda series of video games. In each case, we prove that the generalized game with that …

We discuss some results on the complexity of games and puzzles. In particular, we focus on
the relationship between bounded treewidth and the (in-) tractability of games and puzzles …

Since the turn of the 21st century, seeing the decline of Moore's Law on the horizon, the
pursuit of continued software performance gains has led to the prominence of computer …