Phase transitions and the search problem

by: Tad Hogg, Bernardo A Huberman, Colin P Williams

Artificial Intelligence, Vol. 81, No. 1-2. (March 1996), pp. 1-15.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

sdvillal

Find related articles with these CiteULike tags

phase-transition

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.

@article{citeulike:2798738, 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.}, author = {Hogg, Tad and Huberman, Bernardo A. and Williams, Colin P. }, booktitle = {Frontiers in Problem Solving: Phase Transitions and Complexity}, citeulike-article-id = {2798738}, doi = {10.1016/0004-3702(95)00044-5}, journal = {Artificial Intelligence}, keywords = {phase-transition}, month = {March}, number = {1-2}, pages = {1--15}, posted-at = {2008-05-14 14:39:31}, priority = {2}, title = {Phase transitions and the search problem}, url = {http://dx.doi.org/10.1016/0004-3702(95)00044-5}, volume = {81}, year = {1996} }

RIS record

TY - JOUR ID - citeulike:2798738 L3 - citeulike-article-id:2798738 TI - Phase transitions and the search problem T2 - Frontiers in Problem Solving: Phase Transitions and Complexity JF - Artificial Intelligence VL - 81 IS - 1-2 SP - 1 EP - 15 N2 - 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. KW - phase-transition AU - Hogg, Tad AU - Huberman, Bernardo AU - Williams, Colin PY - 1996/03// UR - http://dx.doi.org/10.1016/0004-3702(95)00044-5 ER -

RIS BibTeX