التفاصيل البيبلوغرافية
| العنوان: |
Analytic and Algorithmic Solution of Random Satisfiability Problems. |
| المؤلفون: |
Mézard, M., Parisi, G., Zecchina, R. |
| المصدر: |
Science. 8/2/2002, Vol. 297 Issue 5582, p812-815. 4p. 1 Diagram, 1 Graph. |
| مصطلحات موضوعية: |
*ALGORITHMS, *STATISTICAL physics |
| مستخلص: |
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 α[sub 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 α[sub 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. [ABSTRACT FROM AUTHOR] |
| قاعدة البيانات: |
Academic Search Index |
