The Typicality of Phase Transitions in Search

@ARTICLE {
 AUTHOR = "Colin P. Williams and Tad Hogg",
 TITLE = "The Typicality of Phase Transitions in Search",
 JOURNAL = "Computational Intelligence",
 VOLUME = "9",
 NUMBER = "3",
 PAGES = "221-238",
 YEAR = "1993"}

Abstract

Search is fundamental to Artificial Intelligence, and numerous sophisticated search methods have been developed. We present a general, simple model of search processes and use it to analytically determine some typical behavior when applied to large problems. In particular, this identifies abrupt changes in overall search cost as small improvements are made in the underlying method. We also examine the robustness of this model's predictions in a range of more realistic cases. More generally, we introduce a criterion for determining when average case results reflect typical behavior which allows the method developed here to be used for investigating other large-scale behaviors of complex AI systems.
keywords: search, complexity, typicality, phase transitions

A longer version of this paper, with more detailed derivations, is available. (760K)