Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/CCC.2008.35 | IEEE Conference on Computational Complexity |
Keywords | DocType | ISSN |
constraint logic,appropriate complexity class,team multiplayer game,uniform framework,simple game family,game family,existing combinatorial game,turing computation,modeling computation,classic complexity class,different game-theoretic setting,game undecidable,satisfiability,combinatorial games,complexity class,directed graph,model of computation,hardness,logic,computational modeling,law,computational complexity,games,polynomials,turing machines,computer science,economic forecasting,directed graphs,artificial intelligence,automata,game theory,formal logic | Conference | 1093-0159 |
Citations | PageRank | References |
12 | 1.18 | 28 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Robert A. Hearn | 2 | 169 | 20.52 |