Summary Phase Transition Effect

• Coincides with hardest instances.

• Behavior at threshold can be analyzed with tools from statistical physics:

  • Threshold has universal form with predictablecorrections for N (number of vars).
  • Inverse transformation gives 50% point for testing.
    (Also, rescaling cost function; Selman and Kirkpatrick 1995, Gent and Walsh 1995)
    

Previous slide

Next slide

Back to first slide

View graphic version