Statistical mechanics has been applied in a variety of computational situations [17]. Important examples include a transition from polynomial to exponential average search cost depending on the effectiveness of heuristic pruning [27, 47, 51] and another from underconstrained to overconstrained problems [5]. Additional transitions have been identified in models of associative memory [30, 49], automatic planning [3], optimization problems [31, 5, 39, 58] and various cases of pattern matching and classification [52, 22, 15, 36]. Because of the many universal features of phase transitions, their identification in a variety of computational contexts suggests there are a number of phenomenological regularities underlying these problems.
The main focus of this article is on transitions in constraint satisfaction problems [38] for which there has been a great deal of recent work [6, 8, 13, 35, 42, 46, 55, 53, 54, 18]. A particularly surprising result is that hard problem instances are concentrated near the same parameter values for a wide variety of common search heuristics, on average. This location also corresponds to a transition in solubility. This behavior can be readily understood through mean-field theories [56, 50, 6] as due to a competition between increasing pruning of bad search paths and a decreasing number of solutions. These theories also give reasonable quantitative values for the location of transitions and can be improved by including some corrections [54]. These simple but approximate theoretical results contrast with the difficulty of deriving exact results. For example, so far the existence of the transition for the well-studied random satisfiability (SAT) problem has not been formally established, and its location can only be bounded [29, 4] between clause-to-variable ratios of 3 and 4.8 for the case of 3-SAT. In addition to this transition in solubility (or more generally, from under- to overconstrained problems) there are a number of more subtle behaviors. These include transitions from polynomial to exponential average search cost, and the appearance of rare hard cases among underconstrained problems [13, 25] apparently due to infrequent but extreme thrashing by many standard search techniques [1].