{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T01:29:03Z","timestamp":1771723743424,"version":"3.50.1"},"reference-count":59,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1996,3,1]],"date-time":"1996-03-01T00:00:00Z","timestamp":825638400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":6355,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[1996,3]]},"DOI":"10.1016\/0004-3702(95)00044-5","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T04:24:09Z","timestamp":1027657449000},"page":"1-15","source":"Crossref","is-referenced-by-count":154,"title":["Phase transitions and the search problem"],"prefix":"10.1016","volume":"81","author":[{"given":"Tad","family":"Hogg","sequence":"first","affiliation":[]},{"given":"Bernardo A.","family":"Huberman","sequence":"additional","affiliation":[]},{"given":"Colin P.","family":"Williams","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(95)00044-5_BIB1","article-title":"Intelligent backtracking on the hardest constraint problems","author":"Baker","year":"1995","journal-title":"J. Artif. Intett. Res."},{"key":"10.1016\/0004-3702(95)00044-5_BIB2","author":"Bollobas","year":"1985"},{"key":"10.1016\/0004-3702(95)00044-5_BIB3","series-title":"Proceedings AAAI-93","first-page":"480","article-title":"An average case analysis of planning","author":"Bylander","year":"1993"},{"key":"10.1016\/0004-3702(95)00044-5_BIB4","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","article-title":"Probabilistic analysis of a generalization of the unit-clause literal selection heuristics","volume":"51","author":"Chao","year":"1990","journal-title":"Information Sci."},{"key":"10.1016\/0004-3702(95)00044-5_BIB5","series-title":"Proceedings IJCAI-91","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/0004-3702(95)00044-5_BIB6","series-title":"Proceedings Physics of Computation Workshop","first-page":"63","article-title":"Computational complexity and phase transitions","author":"Cheeseman","year":"1992"},{"issue":"2","key":"10.1016\/0004-3702(95)00044-5_BIB7","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1137\/0221022","article-title":"Heuristic sampling: a method for predicting the performance of tree searching programs","volume":"21","author":"Chen","year":"1992","journal-title":"SIAM J. Computing"},{"key":"10.1016\/0004-3702(95)00044-5_BIB8","series-title":"Proceedings AAAI-93","first-page":"21","article-title":"Experimental results on the cross-over point in satisfiability problems","author":"Crawford","year":"1993"},{"key":"10.1016\/0004-3702(95)00044-5_BIB9","series-title":"Percolation Structures and Processes","volume":"5","year":"1983"},{"issue":"4","key":"10.1016\/0004-3702(95)00044-5_BIB10","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1063\/1.1703745","article-title":"Some cluster size and percolation problems","volume":"2","author":"Fisher","year":"1961","journal-title":"J. Math. Phys."},{"key":"10.1016\/0004-3702(95)00044-5_BIB11","article-title":"Phase transitions in NP-hard problem spaces","author":"Frank","year":"1995","journal-title":"Ph.D. Qualifying Exam Paper"},{"key":"10.1016\/0004-3702(95)00044-5_BIB12","author":"Garey","year":"1979"},{"key":"10.1016\/0004-3702(95)00044-5_BIB13","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","article-title":"Easy problems are sometimes hard","volume":"70","author":"Gent","year":"1994","journal-title":"Artif. Intett."},{"key":"10.1016\/0004-3702(95)00044-5_BIB14","author":"Goodstein","year":"1975"},{"key":"10.1016\/0004-3702(95)00044-5_BIB15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0167-8655(91)90032-H","article-title":"A cluster detection algorithm based on percolation theory","volume":"12","author":"Gotsman","year":"1991","journal-title":"Pattern Recogn. Lett."},{"key":"10.1016\/0004-3702(95)00044-5_BIB16","article-title":"Test case generators and computational results for the maximum clique problem","author":"Hasselberg","year":"1992"},{"key":"10.1016\/0004-3702(95)00044-5_BIB17","series-title":"Phase transitions in constraint satisfaction search","author":"Hogg","year":"1994"},{"key":"10.1016\/0004-3702(95)00044-5_BIB18","first-page":"357","article-title":"Applications of statistical mechanics to combinatorial search problems","volume":"2","author":"Hogg","year":"1995"},{"key":"10.1016\/0004-3702(95)00044-5_BIB19","article-title":"Exploiting problem structure as a search heuristic","author":"Hogg","year":"1995"},{"key":"10.1016\/0004-3702(95)00044-5_BIB20","unstructured":"T. Hogg, Quantum computing and phase transitions in combinatorial search, J. Artif. Intell. Res. (to appear)."},{"key":"10.1016\/0004-3702(95)00044-5_BIB21","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0370-1573(87)90096-2","article-title":"Artificial intelligence and large scale computation: A physics perspective","volume":"156","author":"Hogg","year":"1987","journal-title":"Phys. Reports"},{"issue":"4","key":"10.1016\/0004-3702(95)00044-5_BIB22","first-page":"223","article-title":"Phase transitions in high-dimensional pattern classification","volume":"5","author":"Hogg","year":"1990","journal-title":"Comput. Syst. Sci. Eng."},{"key":"10.1016\/0004-3702(95)00044-5_BIB23","series-title":"Proceedings AAAI-93","first-page":"231","article-title":"Solving the really hard problems with cooperative search","author":"Hogg","year":"1993"},{"key":"10.1016\/0004-3702(95)00044-5_BIB24","series-title":"Proceedings AAAI-94","first-page":"331","article-title":"Expected gains from parallelizing constraint solving for hard problems","author":"Hogg","year":"1994"},{"key":"10.1016\/0004-3702(95)00044-5_BIB25","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","article-title":"The hardest constraint problems: a double phase transition","volume":"69","author":"Hogg","year":"1994","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB26","author":"Holland","year":"1975"},{"key":"10.1016\/0004-3702(95)00044-5_BIB27","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(87)90033-6","article-title":"Phase transitions in artificial intelligence systems","volume":"33","author":"Huberman","year":"1987","journal-title":"Artif. Intell."},{"issue":"3","key":"10.1016\/0004-3702(95)00044-5_BIB28","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/0914041","article-title":"A parallel graph coloring heuristic","volume":"14","author":"Jones","year":"1993","journal-title":"SIAM J. Sci. Comput."},{"key":"10.1016\/0004-3702(95)00044-5_BIB29","series-title":"Proceedings 35th Symposium on Foundations of Computer Science","first-page":"592","article-title":"Tail bounds for occupancy and the satisfiability threshold conjecture","author":"Kamath","year":"1994"},{"key":"10.1016\/0004-3702(95)00044-5_BIB30","article-title":"Self-propagating search: A unified theory of memory","author":"Kanerva","year":"1984"},{"key":"10.1016\/0004-3702(95)00044-5_BIB31","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(83)80006-X","article-title":"Searching for an optimal path in a tree with random costs","volume":"21","author":"Karp","year":"1983","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB32","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1016\/0004-3702(95)00044-5_BIB33","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical behavior in the satisfiability of random boolean expressions","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"10.1016\/0004-3702(95)00044-5_BIB34","author":"Koza","year":"1992"},{"key":"10.1016\/0004-3702(95)00044-5_BIB35","series-title":"AAAI Spring Symposium on AI and NP-Hard Problems","article-title":"Evidence for a satisfiability threshold for random 3CNF formulas","author":"Larrabee","year":"1993"},{"issue":"1","key":"10.1016\/0004-3702(95)00044-5_BIB36","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1006\/jvci.1994.1008","article-title":"Applications of the phase transition theory in visual recognition and classifications","volume":"5","author":"Lau","year":"1994","journal-title":"J. Visual Commun. Image Representation"},{"key":"10.1016\/0004-3702(95)00044-5_BIB37","series-title":"Proceedings 2nd DIMACS Challenge","article-title":"Experiments with parallel graph coloring heuristics","author":"Lewandowski","year":"1993"},{"key":"10.1016\/0004-3702(95)00044-5_BIB38","series-title":"Encyclopedia of AI","first-page":"205","article-title":"Constraint satisfaction","author":"Mackworth","year":"1987"},{"key":"10.1016\/0004-3702(95)00044-5_BIB39","series-title":"Proceedings IJCAI-91","first-page":"172","article-title":"An expected-cost analysis of backtracking and non-backtracking algorithms","author":"McDiarmid","year":"1991"},{"key":"10.1016\/0004-3702(95)00044-5_BIB40","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","article-title":"Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems","volume":"58","author":"Minton","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB41","series-title":"Proceedings AAAI-94","first-page":"168","article-title":"Small is beautiful: a brute-force approach to learning first-order formulas","author":"Minton","year":"1994"},{"key":"10.1016\/0004-3702(95)00044-5_BIB42","series-title":"Proceedings AAAI-92","first-page":"459","article-title":"Hard and easy distributions of SAT problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/0004-3702(95)00044-5_BIB43","author":"Nijenhuis","year":"1978"},{"key":"10.1016\/0004-3702(95)00044-5_BIB44","author":"Pearl","year":"1984"},{"key":"10.1016\/0004-3702(95)00044-5_BIB45","author":"Pearl","year":"1988"},{"key":"10.1016\/0004-3702(95)00044-5_BIB46_1","article-title":"An empirical study of phase transitions in binary constraint satisfaction problems","author":"Prosser","year":"1993"},{"key":"10.1016\/0004-3702(95)00044-5_BIB46_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(95)00048-8","volume":"81","author":"Prosser","year":"1996","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB47","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","article-title":"Search rearrangement backtracking and polynomial average time","volume":"21","author":"Purdom","year":"1983","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB48","series-title":"Proceedings AAAI-92","first-page":"440","article-title":"A new method for solving hard satisfiability problems","author":"Selman","year":"1992"},{"key":"10.1016\/0004-3702(95)00044-5_BIB49","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1126\/science.236.4805.1092","article-title":"Observation of phase transitions in spreading activation networks","volume":"236","author":"Shrager","year":"1987","journal-title":"Science"},{"key":"10.1016\/0004-3702(95)00044-5_BIB50","article-title":"The phase transition in constraint satisfaction problems: a closer look at the mushy region","author":"Smith","year":"1994"},{"key":"10.1016\/0004-3702(95)00044-5_BIB51","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1147\/rd.303.0242","article-title":"The average complexity of depth-first search with backtracking and cutoff","volume":"30","author":"Stone","year":"1986","journal-title":"IBM J. Res. Development"},{"key":"10.1016\/0004-3702(95)00044-5_BIB52","first-page":"1239","article-title":"Phase transitions in sequence matches and nucleic acid structure","volume":"84","author":"Waterman","year":"1987"},{"key":"10.1016\/0004-3702(95)00044-5_BIB53","series-title":"Proceedings AAAI-92","first-page":"472","article-title":"Using deep structure to locate hard problems","author":"Williams","year":"1992"},{"key":"10.1016\/0004-3702(95)00044-5_BIB54","series-title":"Proceedings AAAI-93","first-page":"152","article-title":"Extending deep structure","author":"Williams","year":"1993"},{"issue":"3","key":"10.1016\/0004-3702(95)00044-5_BIB55","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1111\/j.1467-8640.1993.tb00307.x","article-title":"The typicality of phase transitions in search","volume":"9","author":"Williams","year":"1993","journal-title":"Comput. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB56","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","article-title":"Exploiting the deep structure of constraint problems","volume":"70","author":"Williams","year":"1994","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(95)00044-5_BIB57","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1038\/scientificamerican0879-158","article-title":"Problems in physics with many scales of length","volume":"241","author":"Wilson","year":"1979","journal-title":"Sci. American"},{"key":"10.1016\/0004-3702(95)00044-5_BIB58","series-title":"Proceedings AAAI-92","first-page":"545","article-title":"An average-case analysis of branch-and-bound with applications: summary of results","author":"Zhang","year":"1992"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370295000445?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370295000445?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T10:27:35Z","timestamp":1555064855000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370295000445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":59,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1996,3]]}},"alternative-id":["0004370295000445"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(95)00044-5","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}