Title

Scaling, Renormalization, and Universality in Combinatorial Games

Document Type

Book

Role

Contributor

Publication

Combinatorial Optimization and Applications

Publisher

Springer-Verlag

Standard Number

978-3-540-73555-7

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.

Share

COinS