Much of the theoretical work on NP search problems examines their worst case behavior. Although these search problems can be very hard, in the worst case, there is a great deal of individual variation in these problems and among different search methods. A number of recent studies of NP search problems have focused on regularities of the typical behavior [7, 40, 53, 27, 25]. This work has identified a number of common behaviors. Specifically, for large problems, a few parameters characterizing their structure determine the relative difficulty for a wide variety of common search methods, on average. Moreover, changes in these parameters give rise to transitions, becoming more abrupt for larger problems, that are analogous to phase transitions in physical systems. In this case, the transition is from underconstrained to overconstrained problems, with the hardest cases concentrated in the transition region. One powerful result of this work is that this concentration of hard cases occurs at the same parameter values for a wide range of search methods. That is, this behavior is a property of the problems rather than of the details of the search algorithm.
This can be understood by viewing a search as making a series of choices until a solution is found. The overall search will usually be relatively easy (i.e., require few steps) if either there are many choices leading to solutions or else choices that do not lead to solutions can be recognized quickly as such, so that unproductive search is avoided. Whether this condition holds is in turn determined by how tightly constrained the problem is. When there are few constraints almost all choices are good ones, leading quickly to a solution. With many constraints, on the other hand, there are few good choices but the bad ones can be recognized very quickly as violating some constraints so that not much time is wasted considering them. In between these two cases are the hard problems: enough constraints so good choices are rare but few enough that bad choices are usually recognized only with a lot of additional search.
A more detailed analysis suggests a series of transitions [28]. With very few constraints, the average search cost scales polynomially. As more constraints are added, there is a transition to exponential scaling. The rate of growth of this exponential increases until the transition region described above is reached. Beyond that point, with its concentration of hard problems, the growth rate decreases. Eventually, for very highly constrained problems, the search cost again grows only polynomially with size.