Applications of Statistical Mechanics to Combinatorial Search Problems

Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com

@INBOOK {
  AUTHOR = "Tad Hogg",
  TITLE = "Applications of Statistical Mechanics to Combinatorial Search Problems",
  BOOKTITLE = "Annual Reviews of Computational Physics",
  EDITOR = "D. Stauffer",
  VOLUME = "2",
  PAGES = "357-406",
  PUBLISHER = "World Scientific",
  ADDRESS = "Singapore",
  YEAR = "1995"
}

The statistical mechanics of combinatorial search problems is described using the example of the well-known NP-complete graph coloring problem. We focus on a recently identified phase transition from under- to overconstrained problems, near which are concentrated many hard to solve search problems. Thus, a readily computed measure of problem structure predicts the difficulty of solving the problem, on average. However, this prediction is associated with a large variance and depends on the somewhat arbitrary choice of the problem ensemble. Thus these results are of limited direct use for individual instances. To help address this limitation, additional parameters, describing problem structure as well as heuristic effectiveness, are introduced. This also highlights the distinction between the statistical mechanics of combinatorial search problems, with their exponentially large search spaces, and physical systems, whose interactions are often governed by a simple euclidean metric.
postcript (969K)