期刊
SCIENCE
卷 297, 期 5582, 页码 812-815出版社
AMER ASSOC ADVANCEMENT SCIENCE
DOI: 10.1126/science.1073287
关键词
-
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据