research topics

Phase Transitions in Search

Easily computed structural parameters of constraint satisfaction 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.

The Artificial Intelligence special issue on Frontiers in Problem Solving: Phase Transitions and Complexity. has a collection of papers on phase transitions in search.

Observations and Theory

• 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
  D. Mammen and T. Hogg, A New Look at the Easy-hard-easy Pattern of Combinatorial Search Difficulty, 1997
• 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

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.

• Cooperative problem solving is a powerful method for approaching difficult problems.
• Simple, independent parallel search is effective for some of the hard problem instances:
  T. Hogg and C. P. Williams, Expected Gains from Parallelizing Constraint Solving for Hard Problems, 1994
• Computational portfolios, analogous to financial portfolios in economics, help solve hard problems:
  B. A. Huberman, R. M. Lukose and T. Hogg, An Economics Approach to Hard Computational Problems, 1997
  summarized in the Research News Story Hedging Bets on Hard Problems

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?

• One example where the phase transition can be used to improve search is in genetic algorithms solving constraint satisfaction problems:
  S. H. Clearwater and T. Hogg, Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms, 1995
• Another example, with more modest improvement, is for backtrack search:
  T. Hogg, Exploiting Problem Structure as a Search Heuristic, 1998

Phase Transitions in General Heuristic Search

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 general discussion of applying analogies from physics to search and other 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

Quantum Computing

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