@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" }

Abstract

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.

pdf (327K)