Performance of Incomplete Search Algorithm
Question: when selecting only the solvable problem instances and solving these problems using an incomplete hill-climbing search algorithm, what kind of problems are most difficult?
Prediction: a problem with fewer solutions (more constrained problem) would be most difficult.
Truth: the problems in the phase transition (PT) region are most difficult (although they have more solutions than the problems beyond PT) [Clark, et al. CP96].