Refining the phase transition in combinatorial search

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.