Walksat Stalls Well Below Satisfiability
Walksat Stalls Well Below Satisfiability
复制标题
步行卫星远低于满意度
DOI：
10.1137/16m1084158
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Hetterich
中科院分区：
文献类型：
--
作者：
A. Coja;A. Haqshenas;S. Hetterich
部分基于物理学的启发式论证，有人提出，某些类型的算法在随机 $k$-SAT 公式上的性能与影响令人满意的分配集的几何形状的相变有关。但是，除了直觉之外，几乎没有严格的证据表明“实用”算法受到这些相变的影响。在本文中，我们证明了 Walksat（一种流行的随机可满足性算法）在不远高于子句/变量密度的随机 $k$-SAT 公式上失败，其中令人满意的分配集破碎成微小的、分离良好的簇。具体来说，我们证明如果 $m/n>c2^k\ln^2k/k$，Walksat 以高概率 (w.h.p.) 无效，其中 $m$ 是子句数量，$n$ 是变量数量，$c>0$ 是绝对常数。相比之下，Walksat 可以在线性时间内找到令人满意的任务。如果 $m/n 0$ [A. Coja-Oghlan 和 A. Frieze，SIAM J. Comput.，43（2...
Partly on the basis of heuristic arguments from physics, it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But, beyond intuition, there has been scant rigorous evidence that “practical” algorithms are affected by these phase transitions. In this paper we prove that Walksat, a popular randomized satisfiability algorithm, fails on random $k$-SAT formulas not very far above clause/variable density, where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove that Walksat is ineffective with high probability (w.h.p.) if $m/n>c2^k\ln^2k/k$, where $m$ is the number of clauses, $n$ is the number of variables, and $c>0$ is an absolute constant. By comparison, Walksat is known to find satisfying assignments in linear time w.h.p. if $m/n 0$ [A. Coja-Oghlan and A. Frieze, SIAM J. Comput., 43 (2...
DOI：
10.1137/12090191x
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
A. Coja-Oghlan;A. Frieze
通讯作者：
A. Coja-Oghlan;A. Frieze