Phase Transitions and the Search Problem

Tad Hogg and Bernardo A. Huberman
Dynamics of Computation
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com and huberman@parc.xerox.com
and
Colin Williams
Knowledge Systems Lab
Stanford University
Stanford, CA 94305
CPWilli118@aol.com

July 1995

Abstract:

We describe how techniques that were originally developed in statistical mechanics can be applied to search problems that arise commonly in artificial intelligence. This approach is useful for understanding the typical behavior of classes of problems. In particular, these techniques predict that abrupt changes in computational cost, analogous to physical phase transitions, should occur universally, as heuristic effectiveness or search space topology is varied. We also present a number of open questions raised by these studies.

• A Statistical View of Search
• Phase Transitions
  • 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?
• Open Issues and Prospects
• References
• About this document ...

An extended version of this paper is the introduction to the special issue of Artificial Intelligence on Frontiers in Problem Solving: Phase Transitions and Complexity, edited by T. Hogg, B. A. Huberman and C. Williams, 81 1-15, 1996.