6 Conclusions

We have presented evidence that the explanation of the easy-hard-easy pattern in solution cost based on a competition between changes in the number of solutions and pruning is insufficient to explain the phenomenon completely for sophisticated search methods. It does explain the overall pattern for problems not restricted by solvability or number of solutions. However, the explanation fails when the number of solutions is held constant and sophisticated search methods are used. In these cases the solution cost peak does not disappear as would be predicted. Alternatively, we can view this explanation as adequate for less sophisticated methods that are not able to readily focus in on unsolvable subproblems encountered during the search.

By considering relatively small search problems, we are able to exhaustively examine the properties of the search space. This allowed us to definitively demonstrate the importance for search behavior of an aspect of problem structure: the size of minimal unsolvable subproblems. Our approach contrasts with much work in this area that involves solving problems as large as feasible within reasonable time bounds. While the latter approach gives a better indication of the asymptotic behavior of the transition, it is not suitable for exhaustive evaluation of the nature of the search spaces encountered, nor for detailed analysis of aspects of individual problem structure.

We believe that detailed examination of the structure of combinatorial problems can yield information about why certain types of problems are difficult or easy. As a class, graph coloring or random CSPs are NP-complete, yet in practice many such problems are actually very easy. In addition, while theoretical work in this area has produced predictions that are asymptotically correct on average, the variance among individual problems in a predicted class is enormous. Increased understanding of the relationships between problem structure, problem solving algorithm, and solution cost is important to determining whether, and if so, how, we can determine prior to problem solving which problems are easy versus infeasibly hard. In contrast to previous theoretical studies that focus on the number of solutions, this work suggests that the size of minimal unsolvable subproblems is an alternate characteristic to study with the potential for producing a more precise characterization of the transition behavior and the nature of hard search problems.

Previous: 5. Minimal Unsolvable Subproblems
Next: 7. Acknowledgements
Return to Contents