Tad Hogg
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@INPROCEEDINGS {,
AUTHOR = "T. Hogg",
TITLE = "Statistical Mechanics of Combinatorial Search",
BOOKTITLE = "Proc. of the Workshop on Physics and Computation, PhysComp94",
PAGES = "196-202",
PUBLISHER = "IEEE Press",
ADDRESS = "Los Alamitos, CA",
YEAR = "1994"}
The statistical mechanics of combinatorial search problems is
described using the example of the well-known NP-complete graph coloring
problem. A simple parameter describing the problem structure predicts
the difficulty of solving the problem, on average. However, because of
the large variance associated with this prediction, it is of limited
direct use for individual instances. Additional parameters, describing
problem structure as well as heuristic effectiveness, are introduced to
address this issue. 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.
keywords: search, complexity, phase transitions, physics of software
postcript (245K, 7 pages, available on-line only within Xerox)