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.

An animated version of the search example described in the paper.

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.

A condensed version of the paper is available in html.