{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T21:05:40Z","timestamp":1648674340922},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[2004,12,31]],"date-time":"2004-12-31T00:00:00Z","timestamp":1104451200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2005,1]]},"DOI":"10.1007\/s10472-005-0426-4","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T19:19:42Z","timestamp":1109791182000},"page":"153-172","source":"Crossref","is-referenced-by-count":0,"title":["Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT"],"prefix":"10.1007","volume":"43","author":[{"given":"Simona","family":"Cocco","sequence":"first","affiliation":[]},{"given":"R\u00e9mi","family":"Monasson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,12,31]]},"reference":[{"key":"426_CR1","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"D. Achlioptas, Lower bounds for random 3-SAT via differential equations, Theoretical Computer Science 265 (2001) 159\u2013185.","journal-title":"Theoretical Computer Science"},{"key":"426_CR2","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, P. Beame and M. Molloy, A sharp threshold in proof complexity, in: Proceedings of STOC \u201801 (2001) pp. 337\u2013346.","DOI":"10.1145\/380752.380820"},{"key":"426_CR3","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and M. Molloy, Analysis of a list-coloring algorithm on a random graph, in: Proceedings of FOCS 97 (1997) pp. 204\u2013212.","DOI":"10.1109\/SFCS.1997.646109"},{"key":"426_CR4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0304-3975(01)00154-2","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"D. Achlioptas, L. Kirousis, E. Kranakis and D. Krizanc, Rigorous results for random (2 + p)-SAT, Theoretical Computer Science 265 (2001) 109\u2013129.","journal-title":"Theoretical Computer Science"},{"key":"426_CR5","first-page":"561","volume-title":"ACM Symp. on Theory of Computing (STOC\u201998)","author":"P. Beame","year":"1998","unstructured":"P. Beame, R. Karp, T. Pitassi and M. Saks, in: ACM Symp. on Theory of Computing (STOC\u201998) (Assoc. Comput. Mach., New York, 1998) 561\u2013571."},{"key":"426_CR6","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M.T. Chao","year":"1986","unstructured":"M.T. Chao and J. Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM Journal on Computing 15 (1986) 1106\u20131118.","journal-title":"SIAM Journal on Computing"},{"key":"426_CR7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"M.T. Chao","year":"1990","unstructured":"M.T. Chao and J. Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem, Information Science 51 (1990) 289\u2013314.","journal-title":"Information Science"},{"key":"426_CR8","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e0tal","year":"1988","unstructured":"V. Chv\u00e0tal and E. Szmeredi, Many hard examples for resolution, Journal of the ACM 35 (1988) 759\u2013768.","journal-title":"Journal of the ACM"},{"key":"426_CR9","doi-asserted-by":"crossref","unstructured":"C. Coarfa, D.D. Dernopoulos, A. San Miguel Aguirre, D. Subramanian and M.Y. Vardi, Random 3-SAT: The plot thickens, in: Proc. Principles and Practice of Constraint Programming (CP\u20192000), ed. R. Dechter, Lecture Notes in Computer Science, Vol. 1894 (2000) pp. 143\u2013159.","DOI":"10.1007\/3-540-45349-0_12"},{"key":"426_CR10","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1103\/PhysRevLett.86.1654","volume":"86","author":"S. Cocco","year":"2001","unstructured":"S. Cocco and R. Monasson, Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-satisfiability problem, Phys. Rev. Lett. 86 (2001) 1654.","journal-title":"Phys. Rev. Lett."},{"key":"426_CR11","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s100510170101","volume":"22","author":"S. Cocco","year":"2001","unstructured":"S. Cocco and R. Monasson, Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms, Eur. Phys. J. B 22 (2001) 505.","journal-title":"Eur. Phys. J. B"},{"key":"426_CR12","doi-asserted-by":"crossref","first-page":"037101","DOI":"10.1103\/PhysRevE.66.037101","volume":"66","author":"S. Cocco","year":"2002","unstructured":"S. Cocco and R. Monasson, Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random satisifiability problem, and its application to stop-and-restart resolutions, Phys. Rev. E 66 (2002) 037101.","journal-title":"Phys. Rev. E"},{"key":"426_CR13","first-page":"21","volume-title":"Experimental results on the cross-over point in satisfiability problems","author":"J. Crawford","year":"1993","unstructured":"J. Crawford and L. Auton, Experimental results on the cross-over point in satisfiability problems, in: Proc. 11th Natl. Conference on Artificial Intelligence (AAAI-93) (The AAAI Press\/MIT Press, Cambridge, MA, 1993) 21\u201327; Artificial Intelligence 81 (1996)."},{"key":"426_CR14","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann and D. Loveland, A machine program for theorem proving, Communications of the ACM 5 (1962) 394\u2013397.","journal-title":"Communications of the ACM"},{"key":"426_CR15","first-page":"415","volume-title":"DIMACS Series in Discrete Math. and Computer Science","author":"O. Dubois","year":"1993","unstructured":"O. Dubois, P. Andre, Y. Boufkhad and J. Carlier, SAT versus UNSAT, in: Second DIMACS Challenge, eds. D.S. Johnson and M.A. Trick, DIMACS Series in Discrete Math. and Computer Science (Amer. Math. Soc., Providence, RI, 1993) 415\u2013436."},{"key":"426_CR16","unstructured":"O. Dubois, Y. Boufkhad and J. Mandler, Typical random 3-SAT formulae and the satisfiability threshold, in: Proc. of ACM-SIAM Symposium on Discrete Algorithms (2000) pp. 126\u2013127."},{"key":"426_CR17","doi-asserted-by":"crossref","unstructured":"O. Dubois, R. Monasson, B. Selman and R. Zecchina (eds.), Phase transitions in combinatorial problems, Theor. Comp. Sci. 265(1\u20132) (2001).","DOI":"10.1016\/S0304-3975(01)00133-5"},{"key":"426_CR18","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(01)00158-X","volume":"265","author":"J. Franco","year":"2001","unstructured":"J. Franco, Results related to thresholds phenomena research in satisfiability: lower bounds, Theor. Comp. Sci. 265 (2001) 147\u2013157.","journal-title":"Theor. Comp. Sci."},{"key":"426_CR19","first-page":"1017","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"E. Friedgut, Sharp thresholds of graph properties, and the k-sat problem, Journal of the AMS 12 (1999) 1017.","journal-title":"Journal of the AMS"},{"key":"426_CR20","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. Frieze","year":"1996","unstructured":"A. Frieze and S. Suen, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms 20 (1996) 312\u2013335.","journal-title":"Journal of Algorithms"},{"key":"426_CR21","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0004-3702(94)90109-0","volume":"70","author":"I.P. Gent","year":"1994","unstructured":"I.P. Gent and T. Walsh, Easy problems are sometimes hard, Artificial Intelligence 70 (1994) 335\u2013345.","journal-title":"Artificial Intelligence"},{"key":"426_CR22","volume-title":"Frontiers in Artificial Intelligence and Applications","author":"I. Gent","year":"2000","unstructured":"I. Gent, H. van Maaren and T. Walsh (eds.), SAT2000: Highlights of Satisfiability Research in the Year 2000, Frontiers in Artificial Intelligence and Applications, Vol. 63 (IOS Press, Amsterdam, 2000)."},{"key":"426_CR23","doi-asserted-by":"crossref","unstructured":"C.P. Gomes, B. Selman, N. Crato and H. Kautz, J. Automated Reasoning 24 (2000) 67.","DOI":"10.1023\/A:1006314320276"},{"key":"426_CR24","doi-asserted-by":"crossref","unstructured":"J. Gu, P.W. Purdom, J. Franco and B.W. Wah, Algorithms for satisfiability (SAT) problem: a survey, in: DIMACS Series on Discrete Mathematics and Theoretical Computer Science, Vol. 35 (American Mathematical Society, 1997) pp. 19\u2013151.","DOI":"10.1090\/dimacs\/035\/02"},{"key":"426_CR25","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1103\/PhysRevLett.86.1658","volume":"86","author":"A. Hartmann","year":"2001","unstructured":"A. Hartmann and M. Weigt, Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs, Phys. Rev. Lett. 86 (2001) 1658.","journal-title":"Phys. Rev. Lett."},{"key":"426_CR26","doi-asserted-by":"crossref","unstructured":"T. Hogg, B.A. Huberman and C. Williams (eds.), Artificial Intelligence 81(1\u20132), Special Issue on Frontiers in Problem Solving: Phase Transitions and Complexity (1996).","DOI":"10.1016\/0004-3702(95)00044-5"},{"key":"426_CR27","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"T. Hogg and C.P. Williams, The hardest constraint problems: a double phase transition, Artificial Intelligence 69 (1994) 359\u2013377.","journal-title":"Artificial Intelligence"},{"key":"426_CR28","doi-asserted-by":"crossref","unstructured":"A.C. Kaporis, L.M. Kirousis and E.G. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, in: ESA (2002) pp. 574\u2013585.","DOI":"10.1007\/3-540-45749-6_51"},{"key":"426_CR29","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions, Science 264 (1994) 1297\u20131301.","journal-title":"Science"},{"key":"426_CR30","first-page":"440","volume-title":"Hard and easy distributions of SAT problems","author":"D. Mitchell","year":"1992","unstructured":"D. Mitchell, B. Selman and H. Levesque, Hard and easy distributions of SAT problems, in: Proc. of the Tenth Natl. Conf. on Artificial Intelligence (AAAI-92) (The AAAI Press\/MIT Press, Cambridge, MA, 1992) 440\u2013446."},{"key":"426_CR31","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, Determining computational complexity from characteristic \u2018phase transitions\u2019, Nature 400 (1999) 133\u2013137.","journal-title":"Nature"},{"key":"426_CR32","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G","volume":"15","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, 2 + p-SAT: Relation of typical-case complexity to the nature of the phase transition, Random Structure and Algorithms 15 (1999) 414.","journal-title":"Random Structure and Algorithms"},{"key":"426_CR33","doi-asserted-by":"crossref","first-page":"178701","DOI":"10.1103\/PhysRevLett.88.178701","volume":"88","author":"A. Montanari","year":"2002","unstructured":"A. Montanari and R. Zecchina, Boosting search by rare events, Phys. Rev. Lett. 88 (2002) 178701.","journal-title":"Phys. Rev. Lett."},{"key":"426_CR34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(95)00056-9","volume":"81","author":"B. Selman","year":"1996","unstructured":"B. Selman and S. Kirkpatrick, Critical behavior in the computational cost of satisfiability testing, Artificial Intelligence 81 (1996) 273\u2013295.","journal-title":"Artificial Intelligence"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-0426-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-005-0426-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-0426-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T02:26:43Z","timestamp":1586140003000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-005-0426-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,31]]},"references-count":34,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["426"],"URL":"https:\/\/doi.org\/10.1007\/s10472-005-0426-4","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12,31]]}}}