Refining the Phase Transitions in Combinatorial Search

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

@ARTICLE {,
 AUTHOR = "Tad Hogg",
 TITLE = "Refining the Phase Transitions in Combinatorial Search",
 JOURNAL = "Artificial Intelligence",
 VOLUEM = "81",
 PAGES = "127-154",
 YEAR = "1996"}

Many recent studies have identified phase transitions from under- to overconstrained instances in classes of constraint satisfaction search problems, and their relation to search cost. For example, cases that are difficult to solve with a variety of search methods are concentrated near these transitions. These studies show that a simple parameter describing the 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 class. 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. These are shown to reduce the variation in some cases. This also provides further insight into the nature of intrinsically hard search problems.