%0 Journal Article %1 Mezard2002Analytic %A Mézard, M. %A Parisi, G. %A Zecchina, R. %D 2002 %I American Association for the Advancement of Science %J Science %K k-sat %N 5582 %P 812--815 %R 10.1126/science.1073287 %T Analytic and Algorithmic Solution of Random Satisfiability Problems %U http://dx.doi.org/10.1126/science.1073287 %V 297 %X We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold αc are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below αc, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.

@article{Mezard2002Analytic, abstract = {{We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold αc are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below αc, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.}}, added-at = {2019-06-10T14:53:09.000+0200}, author = {M\'{e}zard, M. and Parisi, G. and Zecchina, R.}, biburl = {https://www.bibsonomy.org/bibtex/245d69cd2f30e5a7cd58611cb37d52bab/nonancourt}, citeulike-article-id = {2553035}, citeulike-linkout-0 = {http://dx.doi.org/10.1126/science.1073287}, citeulike-linkout-1 = {http://www.sciencemag.org/content/297/5582/812.abstract}, citeulike-linkout-2 = {http://www.sciencemag.org/content/297/5582/812.full.pdf}, citeulike-linkout-3 = {http://www.sciencemag.org/cgi/content/abstract/297/5582/812}, citeulike-linkout-4 = {http://view.ncbi.nlm.nih.gov/pubmed/12089451}, citeulike-linkout-5 = {http://www.hubmed.org/display.cgi?uids=12089451}, day = 02, doi = {10.1126/science.1073287}, interhash = {2f3911dea1139b91109b970a782dbe18}, intrahash = {45d69cd2f30e5a7cd58611cb37d52bab}, issn = {1095-9203}, journal = {Science}, keywords = {k-sat}, month = aug, number = 5582, pages = {812--815}, pmid = {12089451}, posted-at = {2009-07-23 15:53:05}, priority = {2}, publisher = {American Association for the Advancement of Science}, timestamp = {2019-06-10T14:53:09.000+0200}, title = {{Analytic and Algorithmic Solution of Random Satisfiability Problems}}, url = {http://dx.doi.org/10.1126/science.1073287}, volume = 297, year = 2002 }