{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T23:58:08Z","timestamp":1785023888663,"version":"3.55.0"},"reference-count":46,"publisher":"Wiley","issue":"3-4","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"tdm","delay-in-days":5814,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct. Alg."],"published-print":{"date-parts":[[1999,10]]},"DOI":"10.1002\/(sici)1098-2418(199910\/12)15:3\/4<414::aid-rsa10>3.0.co;2-g","type":"journal-article","created":{"date-parts":[[2002,8,25]],"date-time":"2002-08-25T17:04:31Z","timestamp":1030295071000},"page":"414-435","source":"Crossref","is-referenced-by-count":47,"title":["2+p-SAT: Relation of typical-case complexity to the nature of the phase transition"],"prefix":"10.1002","volume":"15","author":[{"given":"R\ufffdmi","family":"Monasson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Riccardo","family":"Zecchina","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Scott","family":"Kirkpatrick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bart","family":"Selman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lidror","family":"Troyansky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","reference":[{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB1","first-page":"108","volume":"85","author":"Hayes","year":"1996","journal-title":"Amer Sci"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB2","first-page":"815","volume-title":"Lectures in the Sciences of Complexity","author":"Fu","year":"1989","unstructured":"and Lectures in the Sciences of Complexity, (Editor), Addison-Wesley, Reading, MA, 1989, p. 815."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB3","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1103\/RevModPhys.70.653","volume":"70","author":"Fisher","year":"1998","journal-title":"Rev Mod Phys"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB4.1","first-page":"264","volume-title":"Proc 7th Int Symp on Mathematical Foundations of Computer Science","author":"Goerdt","year":"1992","unstructured":"Proc 7th Int Symp on Mathematical Foundations of Computer Science, 1992, p. 264;"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB4.2","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","year":"1996","journal-title":"J Comput System Sci"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB4.3","first-page":"620","volume-title":"Proc 33rd IEEE Symp on Foundations of Computer Science","author":"Chv\u00e0tal","year":"1992","unstructured":"and Proc 33rd IEEE Symp on Foundations of Computer Science, 1992, p. 620."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB5","first-page":"151","volume-title":"Proc 3rd Annual ACM Symp on Theory of Computing","author":"Cook","year":"1971","unstructured":"The complexity of theorem-proving procedures, Proc 3rd Annual ACM Symp on Theory of Computing, Association for Computing Machinery, New York, 1971, p. 151."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB6.1","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979","unstructured":"and Computers and Intractability; A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979;"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB6.2","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994","unstructured":"Computational Complexity, Addison-Wesley, Reading, MA, 1994."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB7","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"Aspvall","year":"1979","journal-title":"Inform Process Lett"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB8","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB9","first-page":"439","volume":"6","author":"Kirkpatrick","year":"1993","journal-title":"NIPS Proc"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB10","author":"Friedgut","unstructured":"preprint. Presented at DIMACS 97."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB11","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1145\/276698.276870","author":"Baume","year":"1998","journal-title":"Proc STOC-98"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB12","first-page":"456","author":"Mitchell","year":"1992","journal-title":"Proc American Association for Artificial Intelligence (AAAI-92)"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB13","volume":"81","author":"Hogg","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB14","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(95)00056-9","volume":"81","author":"Selman","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB15","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB16","volume-title":"Introduction to the Theory of Neural Computation","author":"Hertz","year":"1991","unstructured":"and Introduction to the Theory of Neural Computation, Addison-Wesley, Redwood City, CA, 1991."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB17","volume-title":"Spin Glass Theory and Beyond","author":"M\u00e9zard","year":"1987","unstructured":"and Spin Glass Theory and Beyond, World Scientific, Singapore, 1987."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB18","doi-asserted-by":"crossref","first-page":"3881","DOI":"10.1103\/PhysRevLett.76.3881","volume":"76","author":"Monasson","year":"1996","journal-title":"Phys Rev Lett"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB19","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","volume":"56","author":"Monasson","year":"1997","journal-title":"Phys Rev E"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB20","doi-asserted-by":"crossref","first-page":"9209","DOI":"10.1088\/0305-4470\/31\/46\/011","volume":"31","author":"Monasson","year":"1998","journal-title":"J Phys A: Math Gen"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB21","volume-title":"Proc PhysComp96","author":"Monasson","year":"1996","unstructured":"and Phase transition and search cost in the 2+p SAT problem, Proc PhysComp96, Boston, 1996, and (Editors)."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB22","author":"Achlioptas","unstructured":"and Rigorous results for random (2+p)-SAT, submitted for publication. A preliminary version appeared in RALCOM 97."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB23","first-page":"322","volume-title":"Proc 4th Annual ACM-SIAM Symp on Discrete Algorithms","author":"Broder","year":"1993","unstructured":"and Proc 4th Annual ACM-SIAM Symp on Discrete Algorithms, 1993, p. 322."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB24.1","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1080\/13642819808205043","volume":"77","author":"Monasson","year":"1998","journal-title":"Philos Mag B"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB24.2","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1088\/0305-4470\/31\/2\/012","volume":"31","year":"1998","journal-title":"J Phys A"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB25","first-page":"507","volume":"I","author":"Talagrand","year":"1998","journal-title":"Doc Math J DMV"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s004400050147","volume":"110","author":"Talagrand","year":"1998","journal-title":"Probab Theory Related Fields"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB27","author":"Talagrand","journal-title":"Probab Theory Related Fields"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB28","doi-asserted-by":"crossref","first-page":"1983","DOI":"10.1088\/0305-4470\/22\/12\/004","volume":"22","author":"Gardner","year":"1989","journal-title":"J Phys A"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB29","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1109\/PGEC.1965.264137","volume":"EC-14","author":"Cover","year":"1965","journal-title":"IEEE Trans Electron Comput"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB30","doi-asserted-by":"crossref","first-page":"2613","DOI":"10.1103\/PhysRevB.24.2613","volume":"24","author":"Derrida","year":"1981","journal-title":"Phys Rev B"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB31","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/0550-3213(84)90237-2","volume":"240","author":"Gross","year":"1984","journal-title":"Nucl Phys B"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB32","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"Davis","year":"1960","journal-title":"J Assoc Comput Mach"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB33","first-page":"21","volume-title":"Proc AAAI-93, Washington, DC","author":"Crawford","year":"1993","unstructured":"and Experimental results on the cross-over point in satisfiability problems, Proc AAAI-93, Washington, DC, 1993, pp. 21-27."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB34","author":"Van Gelder","journal-title":"J Automat Reason"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB35","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"Frieze","year":"1996","journal-title":"J Algorithms"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB36","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1997.0867","volume":"24","author":"Dubois","year":"1997","journal-title":"J Algorithms"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB37","first-page":"27","volume-title":"Proc 4th European Sympos on Algorithms","author":"Kirousis","year":"1992","unstructured":"and Approximating the unsatisfiability threshold of random formulas, Proc 4th European Sympos on Algorithms, 1992, pp. 27-38."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB38","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"Kamath","year":"1995","journal-title":"Random Struct Alg"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB39","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985","unstructured":"Random Graphs, Academic Press, London, 1985."},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB40","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1209\/epl\/i1997-00379-x","volume":"39","author":"Angl\u00e8s d'Auriac","year":"1997","journal-title":"Europhys Lett"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB41","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1051\/jphys:019850046080127700","volume":"46","author":"Kirkpatrick","year":"1985","journal-title":"J Physique"},{"key":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G-BIB42","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0010-4655(96)00062-8","volume":"96","author":"Schneider","year":"1996","journal-title":"Comput Phys Comm"}],"container-title":["Random Structures and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2F(SICI)1098-2418(199910%2F12)15:3%2F4%3C414::AID-RSA10%3E3.0.CO;2-G","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full\/10.1002\/(SICI)1098-2418(199910\/12)15:3\/4%3C414::AID-RSA10%3E3.0.CO;2-G","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T06:29:22Z","timestamp":1625120962000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,10]]},"references-count":46,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1999,10]]}},"URL":"https:\/\/doi.org\/10.1002\/(sici)1098-2418(199910\/12)15:3\/4<414::aid-rsa10>3.0.co;2-g","relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,10]]}}}