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.
- A tutorial on phase transitions in search:
T.
Hogg, B. A. Huberman and C. Williams, Phase Transitions and the Search
Problem, 1996
- A theory describing why the phase transitions
occur and the approximate location of the transition point, with comparison to empirical
observations and extensions to a variety of search problems:
C.
P. Williams and T. Hogg, Exploiting the Deep Structure of Constraint Problems,
1994
- Hard problems are concentrated around the phase transition, but there are
also rare, extremely hard cases far from the transition region, indicating
more complex behaviors:
T.
Hogg and C. P. Williams, The Hardest Constraint Problems: A Double Phase
Transition, 1994
- A review of the phase transition examining problem classes representing some more realistic types of constraint situations:
T.
Hogg, Applications of Statistical Mechanics to Combinatorial Search Problems,
1995
- Analysis of the structure of hard problems using approximate entropy:
T.
Hogg, Which Search Problems Are Random?, 1998
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.
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?
Other types of phase transitions can also appear in more general searches.
- Phase transitions in heuristic backtrack search:
B.
A. Huberman and T. Hogg, Phase Transitions in Artificial Intelligence Systems,
1987
- An extended analysis of phase transitions in heuristic backtrack search:
C.
P. Williams and T. Hogg, The Typicality of Phase Transitions in Search,
1993
- Phase transitions can also appear in the behavior of database retrieval:
T.
Hogg and J. O. Kephart, Phase Transitions in High-Dimensional Pattern
Classification, 1990
and in spreading activation networks:
J.
Shrager, T. Hogg and B. A. Huberman, Observation of Phase Transitions in
Spreading Activation Networks, 1987
- A more general discussion of analogies from physics applying to search and
other computational problems in artificial intelligence:
T.
Hogg and B. A. Huberman, Artificial Intelligence and Large Scale Computation:
A Physics Perspective, 1987
- Statistical models also describe learning behavior (for people as well as
sophisticated search methods) such as the power law of practice:
J.
Shrager, T. Hogg and B. A. Huberman, A Graph-Dynamic Model of the Power Law of
Practice and the Problem-Solving Fan-Effect, 1988
These papers also contain numerous references to other studies of the phase
transition behavior.
Phase transitions also appear in search
algorithms for quantum computers using problem structure.
home