{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T19:21:44Z","timestamp":1697138504492},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>In this work we suggest a new model for generating random satisfiable<jats:italic>k<\/jats:italic>-CNF formulas. To generate such formulas. randomly permute all<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548309990356_inline1\"><jats:alt-text>$2^k\\binom{n}{k}$<\/jats:alt-text><\/jats:inline-graphic>possible clauses over the variables<jats:italic>x<\/jats:italic><jats:sub>1<\/jats:sub>,.\u00a0.\u00a0.,<jats:italic>x<jats:sub>n<\/jats:sub><\/jats:italic>, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if, after its addition, the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first<jats:italic>m<\/jats:italic>clauses (in the random permutation's order).<\/jats:p><jats:p>Random processes with conditioning on a certain property being respected are widely studied in the context of graph properties. This study was pioneered by Ruci\u0144ski and Wormald in 1992 for graphs with a fixed degree sequence, and also by Erd\u0151s, Suen and Winkler in 1995 for triangle-free and bipartite graphs. Since then many other graph properties have been studied, such as planarity and<jats:italic>H<\/jats:italic>-freeness. Thus our model is a natural extension of this approach to the satisfiability setting.<\/jats:p><jats:p>Our main contribution is as follows. For<jats:italic>m<\/jats:italic>\u2265<jats:italic>cn<\/jats:italic>,<jats:italic>c<\/jats:italic>=<jats:italic>c<\/jats:italic>(<jats:italic>k<\/jats:italic>) a sufficiently large constant, we are able to characterize the structure of the solution space of a typical formula in this distribution. Specifically, we show that typically all satisfying assignments are essentially clustered in one cluster, and all but<jats:italic>e<\/jats:italic><jats:sup>\u2212\u03a9(<jats:italic>m<\/jats:italic>\/<jats:italic>n<\/jats:italic>)<\/jats:sup><jats:italic>n<\/jats:italic>of the variables take the same value in all satisfying assignments. We also describe a polynomial-time algorithm that finds w.h.p. a satisfying assignment for such formulas.<\/jats:p>","DOI":"10.1017\/s0963548309990356","type":"journal-article","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T10:38:15Z","timestamp":1250764695000},"page":"775-801","source":"Crossref","is-referenced-by-count":7,"title":["On the Random Satisfiable Process"],"prefix":"10.1017","volume":"18","author":[{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAN","family":"VILENCHIK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"key":"S0963548309990356_ref10","doi-asserted-by":"crossref","unstructured":"[10] Cook S. (1971) The complexity of theorem-proving procedures. In Proc. 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"S0963548309990356_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200101)18:1<61::AID-RSA5>3.0.CO;2-T"},{"key":"S0963548309990356_ref12","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/11830924_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Feige","year":"2006"},{"key":"S0963548309990356_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24605-3_2"},{"key":"S0963548309990356_ref22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"S0963548309990356_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20152"},{"key":"S0963548309990356_ref16","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4347.001.0001","volume-title":"Low-Density Parity-Check Codes","author":"Gallager","year":"1963"},{"key":"S0963548309990356_ref14","unstructured":"[14] Flaxman A. (2003) A spectral technique for random satisfiable 3CNF formulas. In Proc. 14th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 357\u2013363."},{"key":"S0963548309990356_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20186"},{"key":"S0963548309990356_ref1","doi-asserted-by":"crossref","unstructured":"[1] Achlioptas D. and Coja-Oghlan A. (2008) Algorithmic barriers from phase transitions. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 793\u2013802.","DOI":"10.1109\/FOCS.2008.11"},{"key":"S0963548309990356_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"S0963548309990356_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060217"},{"key":"S0963548309990356_ref24","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl","year":"1988"},{"key":"S0963548309990356_ref15","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"S0963548309990356_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08442-8_114"},{"key":"S0963548309990356_ref19","doi-asserted-by":"crossref","unstructured":"[19] Krivelevich M. and Vilenchik D. (2006) Solving random satisfiable 3CNF formulas in expected polynomial time. In Proc. 17th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 454\u2013463.","DOI":"10.1145\/1109557.1109608"},{"key":"S0963548309990356_ref25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000183"},{"key":"S0963548309990356_ref8","first-page":"121","volume-title":"Proc. 24th Symposium on Theoretical Aspects of Computer Science","author":"Coja-Oghlan","year":"2007"},{"key":"S0963548309990356_ref13","unstructured":"[13] Feige U. and Vilenchik D. (2004) A local search algorithm for 3SAT. Technical report, The Weizmann Institute of Science."},{"key":"S0963548309990356_ref2","doi-asserted-by":"crossref","unstructured":"[2] Achlioptas D. and Ricci-Tersenghi F. (2006) On the solution-space geometry of random constraint satisfaction problems. In Proc. 38th ACM Symposium on Theory of Computing, pp. 130\u2013139.","DOI":"10.1145\/1132516.1132537"},{"key":"S0963548309990356_ref5","unstructured":"[5] Ben-Sasson E. , Bilu Y. and Gutfreund D. (2002) Finding a randomly planted assignment in a random 3CNF. Manuscript."},{"key":"S0963548309990356_ref21","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1993"},{"key":"S0963548309990356_ref9","doi-asserted-by":"crossref","unstructured":"[9] Coja-Oghlan A. , Krivelevich M. and Vilenchik D. (2007) Why almost all satisfiable k-CNF formulas are easy. In 13th Conference on Analysis of Algorithms: DMTCS Proceedings, pp. 89\u2013102.","DOI":"10.46298\/dmtcs.3538"},{"key":"S0963548309990356_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"S0963548309990356_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T11:46:25Z","timestamp":1685101585000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990356\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["S0963548309990356"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990356","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}