Complexity-theoretic models of phase transitions in search problems

In recent years, numerous studies have observed that many hard combinatoria l decision problems exhibit behaviour described as a 'phase-transition'. Th is is the phenomenon whereby typical instances of a problem display a drama tic shift in certain characteristics as some parameter of the instances is varied. Such characteristics include the likelihood of an instance having a solution and the time taken by a search algorithm. The apparent pervasiven ess of phase-transitions in hard combinatorial search problems has led to c ontrasting claims being advanced concerning to what extent all NP-complete problems exhibit phase-transitions. The established importance of exploitin g phase-transition effects in the design of search heuristics provides a st rong motivation for assessing how valid such claims may be. In this paper w e argue that questions concerning the generality of phase-transition phenom ena are, at present, ill-defined. In order to address this difficulty, we p ropose and examine rigorous complexity-theoretic models of the statement 't he decision problem D has a phase-transition'. Within these models it is pr oved that for certain 'natural' definitions contrasting results about phase -transition behaviour can be proved. (C) 2000 Elsevier Science B.V. All rig hts reserved.