{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T19:45:52Z","timestamp":1720640752925},"reference-count":19,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2001,6]]},"DOI":"10.1016\/s1571-0653(04)00312-9","type":"journal-article","created":{"date-parts":[[2005,4,9]],"date-time":"2005-04-09T13:34:04Z","timestamp":1113053644000},"page":"36-47","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Statistical physics analysis of the backtrack resolution of random 3-SAT instances"],"prefix":"10.1016","volume":"9","author":[{"given":"Simona","family":"Cocco","sequence":"first","affiliation":[]},{"given":"R\u00e9mi","family":"Monassonb","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00312-9_BIB1","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theorem proving","volume":"5","author":"Davis","year":"1962","journal-title":"Communications of the ACM"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1090\/dimacs\/035\/02","article-title":"Algorithms for satisfiability (SAT) problem: a survey","volume":"35","author":"Gu","year":"1997","journal-title":"DIMACS Series on Discrete Mathematics and Theoretical Computer Science"},{"issue":"I &: II","key":"10.1016\/S1571-0653(04)00312-9_BIB3","article-title":"Frontiers in problem solving: phase transitions and complexity","volume":"81","author":"Hogg","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB4","volume":"vol. 63","year":"2000"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB5","series-title":"Proc. of the Tenth Natl. Conf. on Artificial Intelligence (AAACI-92)","first-page":"440","article-title":"Hard and Easy Distributions of SAT Problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB6","unstructured":"J. Crawford, L. Auton, Experimental Results on the Cross-Over Point in Satisfiability Problems, Proc. 11th Natl. Conference on Artificial Intelligence (AAAI-93), 21-27, The AAAI Press \/ MIT Press. Cambridge, MA (1993); Artificial Intelligence 81 (1996)."},{"key":"10.1016\/S1571-0653(04)00312-9_BIB7","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":"Selman","year":"1994","journal-title":"Science"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB8","first-page":"1017","article-title":"Sharp thresholds of graph properties, and the k-sat problem","volume":"12","author":"Friedgu","year":"1999","journal-title":"Journal of the A.M.S."},{"key":"10.1016\/S1571-0653(04)00312-9_BIB9","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","article-title":"Determining computational complexity from characteristic \u2018phase transitions\u2019","volume":"400","author":"Monasson","year":"1999","journal-title":"Nature"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB10","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","article-title":"Many hard examples for resolution","volume":"35","author":"Chv\u00e0tal","year":"1988","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB11","doi-asserted-by":"crossref","unstructured":"An account of our results intended to a physicists audience has been presented in: S. Cocco R. Monasson, Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem. Phys. Rev. Lett. 86, 1654 (2001); Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms, cond-mat preprint library, http:\/\/arXiv.org\/abs\/cond-mat\/0012191(2000)","DOI":"10.1103\/PhysRevLett.86.1654"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB12","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1103\/PhysRevLett.86.1658","article-title":"Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs","volume":"86","author":"Hartmann","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S1571-0653(04)00312-9_BIB13","article-title":"Rigorous results for random (2+p)-SAT","author":"Achlioptas","year":"2001","journal-title":"special issue of Theoretical Computer Science on \u201cNP-hardness and Phase transitions\u201d, to appear"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB14","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0215080","article-title":"Probabilistic analysis of two heuristics for the 3-satisfiability problem","volume":"15","author":"Chao","year":"1986","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB15","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 for the k-satisfiability problem","volume":"51","author":"Chao","year":"1990","journal-title":"Information Science"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB16","article-title":"Lower bounds for random 3-SAT via differential equations","author":"Achliopta","year":"2001","journal-title":"special issue of Theoretical Computer Science on \u201cNP-hardness and Phase transitions\u201d, to appear"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB17","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","article-title":"Analysis of two simple heuristics on a random instance of k-SAT","volume":"20","author":"Frieze","year":"1996","journal-title":"Journal of Algorithms"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB18","volume":"vol. 344","year":"1995"},{"key":"10.1016\/S1571-0653(04)00312-9_BIB19","series-title":"ACM Symp. on Theory of Computing (STOC98)","first-page":"561","author":"Beame","year":"1998"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304003129?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304003129?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,10]],"date-time":"2019-02-10T15:48:34Z","timestamp":1549813714000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304003129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":19,"alternative-id":["S1571065304003129"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00312-9","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2001,6]]}}}