 |
Abstract: One can frame a game or a puzzle as a decision problem: from this configuration, does the puzzle have a solution? Can Black win the game? The computational complexity of the decision problem can then be investigated. I will begin by reviewing the properties of Turing machines and of the complexity classes I'll be discussing (NP-complete, PSPACE-complete, etc.), then briefly present several recent hardness results, including sliding-block puzzles, sliding-coin puzzles, TipOver, Rush Hour, Sokoban, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane.
These results are all applications of a larger framework of computation in terms of generalized games (as opposed to Turing machines), called Constraint Logic. In this framework, cellular automata are zero-player games, puzzles are one-player games, and ordinary games are two-player games. Surprisingly, some team games turn out to be undecidable, even though they are played with finite physical resources.
Joint work with Erik Demaine and others.
This talk will be accessible to graduate students.
|