Information

Abstract

Why are some games hard to play well? The study of computational complexity gives one answer: the games encode long computations.

Any computation can be interpreted as an abstract game. Playing the game perfectly requires performing the computation. Remarkably, some natural games can encode these abstract games and thus simulate general computations. The more complex the game, the more complex the computations it can encode; games that can encode intractable problems are themselves intractable.

I will describe how games can encode computations, and discuss some examples of both provably hard games (checkers, chess, go, etc.) and games that are believed to be hard (hex, jigsaw puzzles, etc.).