Background: Phase Transition
By adding more constraints, the provability that a problem has a solution decreases very rapidly at some point (phase transition)
The problems around the PT region are most difficult for complete search algorithms.
- A solution can be found easily in under-constrained region.
- Most of branches of the search tree can be pruned in over-constrained region.