Scaling, Renormalization, and Universality in Combinatorial Games
Document Type
Book Chapter
Role
Contributor
Published In
Combinatorial Optimization and Applications
Publisher
Springer-Verlag
Volume
4616
First Page
200
Last Page
207
Publication Date
2007
Abstract
Combinatorial games pose an extreme challenge to combinatorial optimization. Several combinatorial games have been shown to be PSPACE-hard and many more are believed to be so. In this paper, we present a new approach to analyzing combinatorial games, which differs dramatically from current approaches. Using the combinatorial game Chomp as a model system, we employ ideas from physics and dynamical systems theory to unveil deep connections between such games and nonlinear phenomena commonly seen in nature.
Suggested Citation
E.J. Friedman and A.S. Landsberg . (2007). Scaling, Renormalization, and Universality in Combinatorial Games. in Combinatorial Optimization and Applications A. Dress et al., eds., Springer-Verlag.
