Analytic and algorithmic solution of random satisfiability problems
Analytic and algorithmic solution of random satisfiability problems
复制标题
DOI：
10.1126/science.1073287
复制
发表时间：
2002-08-02
期刊：
影响因子：
56.9
通讯作者：
Zecchina, R
中科院分区：
文献类型：
--
作者：
Mézard, M;Parisi, G;Zecchina, R
我们研究了由多个子句构建的随机布尔表达式的可满足性（K-可满足性）。子句与变量的比率α小于阈值α（c）的表达式几乎总是可满足的，而比率大于该阈值的表达式几乎总是不可满足的。我们表明存在一个中间阶段低于alpha（c），亚稳态的扩散是负责搜索算法的复杂性发病。我们介绍了一类优化算法，可以处理这些亚稳态，这样的算法已经成功地测试了现有的最大的基准K-可满足性。
We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio alpha of clauses to variables less than a threshold alpha(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 alpha(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.