Paper by Erik D. Demaine
- 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.
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.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by