Phase Transitions in Search

Many studies of constraint satisfaction problems have demonstrated, both empirically and theoretically, that easily computed structural parameters of these problems can predict, on average, how hard the problems are to solve by a variety of search methods.

A major result of this work is that hard instances of NP-complete problems are concentrated near an abrupt transition between under- and overconstrained problems. This transition is analogous to phase transitions seen in some physical systems.

Contents of this page:

For a collection of papers on phase transitions in search, see the Artificial Intelligence special issue on Frontiers in Problem Solving: Phase Transitions and Complexity.

Observations and Theory

Search Methods for Hard Problems

The existence of regions of hard and easy problems raises the question of whether some search methods are particularly well suited for the hard instances.

Using Phase Transitions as a Search Heuristic

The phase transition relates problem structure with likely search cost. From a practical point of view, can knowledge of the phase transition be exploited directly as a search heuristic?

Phase Transitions in General Heuristic Search

Other types of phase transitions can also appear in more general searches.

These papers also contain numerous references to other studies of the phase transition behavior.

Quantum Computing

Phase transitions also appear in search algorithms for quantum computers using problem structure.

Other Places to Visit