Games, Puzzles, and Computation
Speaker: Bob Hearn , Project MAC, CSAIL, MIT
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. We would like to know whether the game is polynomial, NP-complete, PSPACE-complete, etc. Hardness proofs involve constructing "gadgets", which often resemble computational elements. For a large class of games and puzzles, an assembly of such gadgets can be viewed as a kind of computer. But usually the computer is not an ordinary, deterministic Turing machine, and is instead more like a nondeterministic TM, or an alternating TM, etc. However, it's possible to interpret the hardness framework for the game or puzzle itself as the model of computation, rather than the corresponding Turing machine, and it is this idea I would like to explore.