{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:04:37Z","timestamp":1772611477471,"version":"3.50.1"},"reference-count":26,"publisher":"Proceedings of the National Academy of Sciences","issue":"40","content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2008,10,7]]},"abstract":"<jats:p>\n            We study the performance of stochastic local search algorithms for random instances of the\n            <jats:italic>K<\/jats:italic>\n            -satisfiability (\n            <jats:italic>K<\/jats:italic>\n            -SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large\n            <jats:italic>K<\/jats:italic>\n            -SAT instances almost surely in linear time, up to high clause-to-variable ratios \u03b1; for example, for\n            <jats:italic>K<\/jats:italic>\n            = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.\n          <\/jats:p>","DOI":"10.1073\/pnas.0712263105","type":"journal-article","created":{"date-parts":[[2008,10,2]],"date-time":"2008-10-02T01:52:07Z","timestamp":1222912327000},"page":"15253-15257","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":38,"title":["Circumspect descent prevails in solving random constraint satisfaction problems"],"prefix":"10.1073","volume":"105","author":[{"given":"Mikko","family":"Alava","sequence":"first","affiliation":[{"name":"*Department of Engineering Physics, Helsinki University of Technology, P.O. Box 1100, FI-02015, Espoo, Finland;"}]},{"given":"John","family":"Ardelius","sequence":"additional","affiliation":[{"name":"Swedish Institute of Computer Science AB, SE-164 29 Kista, Sweden;"},{"name":"Department of Computational Biology, AlbaNova University Centre, SE-106 91 Stockholm, Sweden;"}]},{"given":"Erik","family":"Aurell","sequence":"additional","affiliation":[{"name":"Department of Computational Biology, AlbaNova University Centre, SE-106 91 Stockholm, Sweden;"},{"name":"Linnaeus Centre, KTH-Royal Institute of Technology, SE-100 44 Stockholm, Sweden;"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology (HIIT), Department of Computer Science, University of Helsinki, P.O.Box 68, FI-00014, Helsinki, Finland;"}]},{"given":"Supriya","family":"Krishnamurthy","sequence":"additional","affiliation":[{"name":"Swedish Institute of Computer Science AB, SE-164 29 Kista, Sweden;"},{"name":"**School of Information and Communication Technology, KTH-Royal Institute of Technology, SE-164 40 Kista, Sweden; and"}]},{"given":"Pekka","family":"Orponen","sequence":"additional","affiliation":[{"name":"Department of Information and Computer Science, Helsinki University of Technology, P.O. Box 5400, FI-02015, Espoo, Finland"}]},{"given":"Sakari","family":"Seitz","sequence":"additional","affiliation":[{"name":"*Department of Engineering Physics, Helsinki University of Technology, P.O. Box 1100, FI-02015, Espoo, Finland;"},{"name":"Department of Information and Computer Science, Helsinki University of Technology, P.O. Box 5400, FI-02015, Espoo, Finland"}]}],"member":"341","published-online":{"date-parts":[[2008,10,7]]},"reference":[{"key":"e_1_3_3_1_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979","unstructured":"MR Garey, DS Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979)."},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/035"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00149-9"},{"key":"e_1_3_3_4_2","first-page":"265","article-title":"Special Issue on NP-Hardness and Phase Transitions","author":"Dubois O","year":"2001","unstructured":", eds O Dubois, R Monasson, B Selman, R Zecchina, Special Issue on NP-Hardness and Phase Transitions. Theor Comput Sci, pp. 265 (2001).","journal-title":"Theor Comput Sci"},{"key":"e_1_3_3_5_2","first-page":"459","volume-title":"Hard and Easy Distributions of SAT Problems","author":"Mitchell D","year":"1992","unstructured":"D Mitchell, B Selman, H Levesque Hard and Easy Distributions of SAT Problems (AAAI Press, San Jose, CA), pp. 459\u2013465, AAAI-92. (1992)."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"e_1_3_3_8_2","volume-title":"Local Search for Combinatorial Optimization","author":"Aarts E","year":"1997","unstructured":", eds E Aarts, JK Lenstra (Wiley, New York Local Search for Combinatorial Optimization, 1997)."},{"key":"e_1_3_3_9_2","volume-title":"Stochastic Local Search: Foundations and Applications","author":"Hoos HH","year":"2005","unstructured":"HH Hoos, T St\u00fctzle Stochastic Local Search: Foundations and Applications (Elsevier, Amsterdam, 2005)."},{"key":"e_1_3_3_10_2","first-page":"50","volume-title":"Ten Challenges in Propositional Reasoning and Search","author":"Selman B","year":"1997","unstructured":"B Selman, H Kautz, D McAllester Ten Challenges in Propositional Reasoning and Search (Elsevier, Amsterdam), pp. 50\u201354, IJCAI-97. (1997)."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.10.004"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185365"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.066104"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.066103"},{"key":"e_1_3_3_16_2","first-page":"521","volume-title":"Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Selman B","year":"1996","unstructured":"B Selman, H Kautz, B Cohen Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, eds DS Johnson, MA Trick (Am Math Soc, Providence RI) Vol 26, 521\u2013532 (1996)."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.037702"},{"key":"e_1_3_3_18_2","first-page":"49","volume-title":"Comparing Beliefs, Surveys and Random Walks","author":"Aurell E","year":"2005","unstructured":"E Aurell, U Gordon, S Kirkpatrick Comparing Beliefs, Surveys and Random Walks (MIT Press, Boston) Vol 17, 49\u201356, Advances in Neural Information Processing Systems (NIPS-04). (2005)."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/06\/P06006"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20090"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.015103"},{"key":"e_1_3_3_24_2","article-title":"On local equilibrium equations for clustering states","author":"Parisi G","year":"2002","unstructured":"G Parisi, On local equilibrium equations for clustering states. Technical Report, cs.CC\/0212047. Available at http:\/\/arxiv.org\/abs\/cs\/0212047. (2002).","journal-title":"Technical Report"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-007-9417-7"},{"key":"e_1_3_3_26_2","first-page":"217","volume-title":"Survey Propagation Revisited","author":"Kroc L","year":"2007","unstructured":"L Kroc, A Sabharwal, B Selman Survey Propagation Revisited (AUAI Press, Arlington, VA), pp. 217\u2013226 (2007)."}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.0712263105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T19:52:11Z","timestamp":1649793131000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.0712263105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,7]]},"references-count":26,"journal-issue":{"issue":"40","published-print":{"date-parts":[[2008,10,7]]}},"alternative-id":["10.1073\/pnas.0712263105"],"URL":"https:\/\/doi.org\/10.1073\/pnas.0712263105","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,7]]},"assertion":[{"value":"2008-01-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}