Thu, 21 Aug 2008 15:35:16 BST CiteULike: sdvillal phase-transition http://www.citeulike.org/user/sdvillal/tag/phase-transition CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/sdvillal/article/2798738 <i>Artificial Intelligence, Vol. 81, No. 1-2. (March 1996), pp. 1-15.</i><br /><br />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. Phase transitions and the search problem Tad Hogg Bernardo Huberman Colin Williams doi:10.1016/0004-3702(95)00044-5 Artificial Intelligence, Vol. 81, No. 1-2. (March 1996), pp. 1-15. 2008-05-14T13:39:17-00:00 1996 Artificial Intelligence 81 1-2 1 15 phase-transition