{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T13:15:48Z","timestamp":1773666948178,"version":"3.50.1"},"reference-count":38,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,8,1]],"date-time":"2001-08-01T00:00:00Z","timestamp":996624000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4368,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,8]]},"DOI":"10.1016\/s0304-3975(01)00154-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:16:57Z","timestamp":1027631817000},"page":"109-129","source":"Crossref","is-referenced-by-count":48,"title":["Rigorous results for random (2+p)-SAT"],"prefix":"10.1016","volume":"265","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lefteris M.","family":"Kirousis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00154-2_BIB1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in: 32nd Ann. ACM Symp. on Theory of Computing, Portland, OR, 2000, ACM, New York, 2000, pp. 28\u201337.","DOI":"10.1145\/335305.335309"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB2","unstructured":"D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, Rigorous results for random (2+p)-SAT, in: RALCOM \u201997, Santorini, 1997, 1997, pp. 1\u201313."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB3","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, Y. Stamatiou, Random constraint satisfaction: a more accurate picture, Constraints, to appear.","DOI":"10.1007\/BFb0017433"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB4","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, M. Molloy, The analysis of a list-coloring algorithm on a random graph, in: 38th Ann. Symp. on Foundations of Computer Science, Miami, FL, 1997, IEEE Comput. Soc. Press, Los Alamitos, CA, 1997, pp. 204\u2013212.","DOI":"10.1109\/SFCS.1997.646109"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB5","first-page":"66","article-title":"Propositional proof complexity: past, present, and future","volume":"65","author":"Beame","year":"1998","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB6","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s100510051065","article-title":"A variational description of the ground state structure in random satisfiability problems","volume":"14","author":"Biroli","year":"2000","journal-title":"Eur. Phys. J. B"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB7","unstructured":"B. Bollob\u00e1s, C. Borgs, J. Chayes, Jeong Han Kim, D.B. Wilson, The scaling window of the 2-SAT transition, 1999, manuscript."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB8","unstructured":"A.Z. Broder, A.M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, in: 4th Ann. ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 1993, ACM, New York, 1993, pp. 322\u2013330."},{"issue":"4","key":"10.1016\/S0304-3975(01)00154-2_BIB9","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 J. Comput."},{"issue":"3","key":"10.1016\/S0304-3975(01)00154-2_BIB10","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":"Inform. Sci."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB11","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal, B. Reed, Mick gets some (the odds are on his side), in: 33th Ann. Symp. on Foundations of Computer Science, Pittsburgh, PA, 1992, IEEE Comput. Soc. Press, Los Alamitos, CA, 1992, pp. 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB12","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedures, in: 3rd Ann. ACM Symp. on Theory of Computing, Shaker Heights, OH, 1971, ACM, New York, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB13","doi-asserted-by":"crossref","unstructured":"S.A. Cook, D.G. Mitchell, Finding hard instances of the satisfiability problem: a survey, in: Satisfiability Problem: Theory and Applications (Piscataway, NJ, 1996), Amer. Math. Soc., Providence, RI, 1997, pp. 1\u201317.","DOI":"10.1090\/dimacs\/035\/01"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB14","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":"Comm. ACM"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"10.1016\/S0304-3975(01)00154-2_BIB16","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1997.0867","article-title":"A general upper bound for the satisfiability threshold of random r-SAT formulae","volume":"24","author":"Dubois","year":"1997","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB17","unstructured":"O. Dubois, Y. Boufkhad, J. Mandler, Typical random 3-SAT formulae and the satisfiability threshold, in: 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, San Francisco, CA, 2000, ACM, New York, 2000, pp. 126\u2013127."},{"issue":"3","key":"10.1016\/S0304-3975(01)00154-2_BIB18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300001590","article-title":"On random 3-sat","volume":"4","author":"El Maftouhi","year":"1995","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB19","unstructured":"W. Fernandez de la Vega, On random 2-SAT, 1992, manuscript."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB20","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF01874393","article-title":"Probabilistic analysis of the pure literal heuristic for the satisfiability problem","volume":"1","author":"Franco","year":"1984","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"10.1016\/S0304-3975(01)00154-2_BIB21","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0166-218X(83)90017-3","article-title":"Probabilistic analysis of the Davis\u2013Putnam procedure for solving the satisfiability problem","volume":"5","author":"Franco","year":"1983","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB22","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","article-title":"Sharp thresholds of graph properties, and the k-SAT problem","volume":"12","author":"Friedgut","year":"1999","journal-title":"J. Amer. Math. Soc."},{"issue":"2","key":"10.1016\/S0304-3975(01)00154-2_BIB23","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":"J. Algorithms"},{"issue":"3","key":"10.1016\/S0304-3975(01)00154-2_BIB24","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","article-title":"A threshold for unsatisfiability","volume":"53","author":"Goerdt","year":"1996","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB25","unstructured":"A. Goldberg, On the complexity of the satisfiability problem, in: 4th Workshop on Automated Deduction, Austin, TX, 1979, 1979, pp. 1\u20136."},{"issue":"2","key":"10.1016\/S0304-3975(01)00154-2_BIB26","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","article-title":"Bounding the unsatisfiability threshold of random 3-SAT","volume":"17","author":"Janson","year":"2000","journal-title":"Random Structures Algorithms"},{"issue":"1","key":"10.1016\/S0304-3975(01)00154-2_BIB27","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","article-title":"Tail bounds for occupancy and the satisfiability threshold conjecture","volume":"7","author":"Kamath","year":"1995","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB28","unstructured":"A.C. Kaporis, L.M. Kirousis, Y. Stamatiou, M. Vamvakari, M. Zito, The unsatisfiability threshold revisited, submitted."},{"issue":"3","key":"10.1016\/S0304-3975(01)00154-2_BIB29","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","article-title":"Approximating the unsatisfiability threshold of random formulas","volume":"12","author":"Kirousis","year":"1998","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0304-3975(01)00154-2_BIB30","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1017\/S096354830000016X","article-title":"On a correlation inequality of Farr","volume":"1","author":"McDiarmid","year":"1992","journal-title":"Combin. Probab. Comput."},{"issue":"21","key":"10.1016\/S0304-3975(01)00154-2_BIB31","doi-asserted-by":"crossref","first-page":"3881","DOI":"10.1103\/PhysRevLett.76.3881","article-title":"Entropy of the K-satisfiability problem","volume":"76","author":"Monasson","year":"1996","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"10.1016\/S0304-3975(01)00154-2_BIB32","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","article-title":"Statistical mechanics of the random K-satisfiability model","volume":"56","author":"Monasson","year":"1997","journal-title":"Phys. Rev. E"},{"issue":"46","key":"10.1016\/S0304-3975(01)00154-2_BIB33","doi-asserted-by":"crossref","first-page":"9209","DOI":"10.1088\/0305-4470\/31\/46\/011","article-title":"Tricritical points in random combinatorics","volume":"31","author":"Monasson","year":"1998","journal-title":"J. Phys. A: Math. and Gen."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB34","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky, Phase transition and search cost in the (2+p)-SAT problem, 4th Workshop on Physics and Computation, Boston, MA, 1996."},{"issue":"6740","key":"10.1016\/S0304-3975(01)00154-2_BIB35","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","article-title":"Determining computational complexity from characteristic \u201cphase transitions\u201d","volume":"400","author":"Monasson","year":"1999","journal-title":"Nature"},{"issue":"1\u20132","key":"10.1016\/S0304-3975(01)00154-2_BIB36","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","article-title":"Generating hard satisfiability problems","volume":"81","author":"Selman","year":"1996","journal-title":"Artificial Intelligence"},{"issue":"4","key":"10.1016\/S0304-3975(01)00154-2_BIB37","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","article-title":"Differential equations for random processes and random graphs","volume":"5","author":"Wormald","year":"1995","journal-title":"Ann. Appl. Probab."},{"key":"10.1016\/S0304-3975(01)00154-2_BIB38","unstructured":"M. Zito, Randomised techniques in combinatorial algorithmics, Ph.D. Thesis, Department of Computer Science, University of Warwick, 1999."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001542?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001542?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T16:24:09Z","timestamp":1580228649000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501001542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,8]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,8]]}},"alternative-id":["S0304397501001542"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00154-2","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,8]]}}}