{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:46Z","timestamp":1787340226204,"version":"build-2736575974"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>Many NP\u2010complete constraint satisfaction problems appear to undergo a \u201cphase transition\u201d from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2\u2010colorability (Property B) and random Not\u2010All\u2010Equal k\u2010SAT is $2^{k-1}\\ln 2 -O(1)$. As a corollary, we establish that the threshold for random k\u2010SAT is of order $\\Theta(2^k)$, resolving a long\u2010standing open problem.<\/jats:p>","DOI":"10.1137\/s0097539703434231","type":"journal-article","created":{"date-parts":[[2006,11,15]],"date-time":"2006-11-15T22:46:25Z","timestamp":1163630785000},"page":"740-762","source":"Crossref","is-referenced-by-count":110,"title":["Random\n                    <i>k<\/i>\n                    \u2010SAT: Two Moments Suffice to Cross a Sharp Threshold"],"prefix":"10.1137","volume":"36","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,10,24]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas,\n                      Setting two variables at a time yields a new lower bound for random 3\u2010SAT\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 28\u201337.","DOI":"10.1145\/335305.335309"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.011"},{"key":"R3","unstructured":"D. Achlioptas, P. Beame, and M. Molloy,\n                      Exponential bounds for DPLL below the satisfiability threshold\n                      , in Proceedings of the Fifteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, New Orleans, 2004, pp. 132\u2013133."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and C. Moore,\n                      \n                        The asymptotic order of the random\n                        k\n                        \u2010SAT threshold\n                      \n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 779\u2013788.","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and C. Moore,\n                      On the 2\u2010colorability of random hypergraphs\n                      , in Randomization and Approximation Techniques in Computer Science, Lecture Notes in Comput. Sci. 2483, Springer\u2010Verlag, Berlin, 2002, pp. 78\u201390.","DOI":"10.1007\/3-540-45726-7_7"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.997"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-04-00464-3"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, A. Naor, and Y. Peres,\n                      On the maximum satisfiability of random formulas\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 362\u2013370.","DOI":"10.1109\/SFCS.2003.1238210"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1335"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and C. Moore,\n                      The chromatic number of random regular graphs\n                      , in Proceedings of the 8th International Workshop on Randomization and Computation, Lecture Notes in Comput. Sci. 3122, Springer\u2010Verlag, Berlin, 2004, pp. 219\u2013228.","DOI":"10.1007\/978-3-540-27821-4_20"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and G. B. Sorkin,\n                      Optimal myopic algorithms for random 3\u2010SAT\n                      , in Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 590\u2013600.","DOI":"10.1109\/SFCS.2000.892327"},{"key":"R12","unstructured":"N. Alon and J. Spencer,\n                      \n                        A Note on Coloring Random\n                        k\n                        \u2010Sets\n                      \n                      , manuscript."},{"key":"R13","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , Wiley & Sons, New York, 1992."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90191-7"},{"key":"R15","first-page":"325","volume":"60","author":"Bernstein F.","year":"1908","journal-title":"Leipz. Ber."},{"key":"R16","unstructured":"A. Z. Broder, A. M. Frieze, and E. Upfal,\n                      \n                        On the satisfiability and maximum satisfiability of random\n                        k\n                        \u2010CNF formulas\n                      \n                      , in Proceedings of the Fourth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Austin, TX, 1993, pp. 322\u2013330."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0215080"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(90)90030-E"},{"key":"R19","unstructured":"P. Cheeseman, R. Kanefsky, and W. Taylor,\n                      Where the really hard problems are\n                      , in Proceedings of the 12th International Joint Conference on Artificial Intelligence, 1991, pp. 331\u2013337."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal and B. Reed,\n                      Mick gets some (the odds are on his side)\n                      , in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"S. A. Cook,\n                      The complexity of theorem\u2010proving procedures\n                      , in Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"R23","unstructured":"N. G. de Bruijn,\n                      Asymptotic Methods in Analysis\n                      , Dover, New York, 1981."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0867"},{"key":"R25","unstructured":"O. Dubois, Y. Boufkhad, and J. Mandler,\n                      Typical random 3\u2010SAT formulae and the satisfiability threshold\n                      , in Electronic Colloquium on Computational Complexity 10, 2003; available online from http:\/\/www.informatik.uni\u2010trier.de\/\u02dcley\/db\/journals\/eccc\/eccc10. html; also available in Proceedings of the Eleventh Annual ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, 2000, pp. 126\u2013127."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001590"},{"key":"R27","first-page":"5","volume":"11","author":"Erdo\u02dds P.","year":"1963","journal-title":"Nordisk Mat. Tidskr."},{"key":"R28","unstructured":"P. Erdo\u02dds and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , in Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. Janos Bolyai 10, North\u2013Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R29","unstructured":"W. Fernandez de la Vega,\n                      On Random 2\u2010SAT\n                      , manuscript, 1992."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90087-3"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90017-3"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0016"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0017-3"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0081"},{"key":"R36","unstructured":"M. Hajiaghayi and G. B. Sorkin,\n                      The satisfiability threshold of random 3\u2010SAT is at least $3.52$\n                      , submitted; available online from http:\/\/www.arxiv.org\/abs\/math. CO\/0310193."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , John Wiley & Sons, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070105"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"A. Kaporis, L. M. Kirousis, and E. Lalas,\n                      Selecting complementary pairs of literals\n                      , in Proceedings of LICS 2003 Workshop on Typical Case Complexity and Phase Transitions, 2003.","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"R42","unstructured":"A. Kaporis, L. M. Kirousis, Y. C. Stamatiou, M. Vamvakari, and M. Zito,\n                      The unsatisfiability threshold revisited\n                      , Discrete Math., to appear."},{"key":"R43","unstructured":"M. Karo\u0144ski and T. \u0141uczak,\n                      Random hypergraphs\n                      , in Combinatorics, Paul Erdo\u02dds Is Eighty, Vol. 2 (Kesztheley, 1993), Bolyai Soc. Math. Stud. 2, Janos Bolyai Math. Soc., Budapest, 1996, pp. 283\u2013293."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<381::AID-RSA5>3.0.CO;2-P"},{"key":"R46","unstructured":"L. Lov\u00e1sz,\n                      Coverings and coloring of hypergraphs\n                      , in Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1973, pp. 3\u201312."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.056126"},{"key":"R49","unstructured":"D. G. Mitchell, B. Selman, and H. J. Levesque,\n                      Hard and easy distributions of SAT problems\n                      , in Proceedings of the 10th National Conference on Artificial Intelligence, 1992, pp. 459\u2013462."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.56.1357"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190090307"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703434231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:54Z","timestamp":1787336754000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703434231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539703434231"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703434231","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}