One of the most dramatic consequences of the statistical approach to computational problems is the identification of situations where small changes in local behavior give especially large changes in global performance. A common case is exponential growth in some variable such as congestion in queues. Another is the appearance of phase transitions, analogous to those in physical systems and certain mathematical models. These abrupt transitions are the subject of this article.

- What Are Phase Transitions?
- How Do Phase Transitions Appear Computationally?
- A Simple Phase Transition
- Phase Transitions in Constraint Satisfaction Problems
- Why Are Phase Transitions Important?

Thu May 16 15:45:43 PDT 1996