Complexity-theoretic models of phase transitions in search problems

AbstractIn recent years, numerous studies have observed that many hard combinatorial decision problems exhibit behaviour described as a ‘phase-transition’. This is the phenomenon whereby typical instances of a problem display a dramatic 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 pervasiveness of phase-transitions in hard combinatorial search problems has led to contrasting claims being advanced concerning to what extent all NP-complete problems exhibit phase-transitions. The established importance of exploiting phase-transition effects in the design of search heuristics provides a strong motivation for assessing how valid such claims may be. In this paper we argue that questions concerning the generality of phase-transition phenomena are, at present, ill-defined. In order to address this difficulty, we propose and examine rigorous complexity-theoretic models of the statement ‘the decision problem D has a phase-transition’. Within these models it is proved that for certain ‘natural’ definitions contrasting results about phase-transition behaviour can be proved