Phase transition behaviour

• Seen in many NP-hard problems

  • SAT, CSP, number partitioning, TSP ...
  • seminal IJCAI-91 paper by Cheeseman, Kanefsky & Taylor

• rapid solubility transition

  • around <Sol> » 1

Previous slide

Next slide

Back to first slide

View graphic version