Scaling, Renormalization, and Universality in Combinatorial Games
Combinatorial Optimization and Applications
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.
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.