Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Robert A. Hearn, “Constraint Logic: A Uniform Framework for Modeling Computation as Games”, in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008), College Park, Maryland, June 23–26, 2008, pages 149–162.

Abstract:

We introduce a simple game family, called Constraint Logic, where players reverse edges in a directed graph while satisfying vertex in-flow constraints. This game family can be interpreted in many different game-theoretic settings, ranging from zero-player automata to a more economic setting of team multiplayer games with hidden information. Each setting gives rise to a model of computation that we show corresponds to a classic complexity class. In this way we obtain a uniform framework for modeling various complexities of computation as games. Most surprising among our results is that a game with three players and a bounded amount of state can simulate any (infinite) Turing computation, making the game undecidable. Our framework also provides a more graphical, less formulaic viewpoint of computation. This graph model has been shown to be particularly appropriate for reducing to many existing combinatorial games and puzzles—such as Sokoban, Rush Hour, River Crossing, TipOver, the Warehouseman's Problem, pushing blocks, hinged-dissection reconfiguration, Amazons, and Konane (Hawaiian Checkers)—which have an intrinsically planar structure. Our framework makes it substantially easier to prove completeness of such games in their appropriate complexity classes.

Availability:

The paper is available in PDF (2615k).

See information on file formats.

[Google Scholar search]

Related papers:

NCL_TCS (PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation)