Belief Propagation Guided Decimation Fails on Random Formulas
Belief Propagation Guided Decimation Fails on Random Formulas
复制标题
信念传播引导抽取在随机公式上失败
DOI：
10.1145/3005398
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
Coja-Oghlan A
中科院分区：
文献类型：
--
作者：
Coja-Oghlan A
令 Φ 为具有 n 个变量和 m 个子句的均匀分布随机 k-SAT 公式。非构造性论证表明 Φ 对于子句/变量比率 m/n⩽rk− SAT∼ 2kln 2 有很高的概率是可满足的。然而，目前尚无有效的算法能够以非零概率找到超出 m/n∼ 2kln (k)/k 的令人满意的分配。基于深刻但非严格的统计力学思想，提出了一种称为置信传播引导抽取的消息传递算法（Mézard，Parisi，Zecchina：Science 2002；Braunstein，Mézard，Zecchina：Random Struc.Algorithm 2005）。实验表明，对于非常接近 tork− SATfork= 3, 4, 5 的密度，该算法可能会成功（Kroc、Sabharwal、Selman：SAC 2009）。在本文中，我们对该算法在非平凡输入分布上进行了首次严格分析，表明置信传播引导抽取无法解决已经形成的随机 k-SAT 公式/n=O(2k/k)，几乎比可满足性阈值 rk− SAT 低 k 倍。事实上，这个证明驳斥了信念传播引导抽取所依赖的一个关键假设。
Let Φ be a uniformly distributed randomk-SAT formula withnvariables andmclauses. Nonconstructive arguments show that Φ is satisfiable for clause/variable ratiosm/n⩽rk− SAT∼ 2kln 2 with high probability. Yet no efficient algorithm is known to find a satisfying assignment beyondm/n∼ 2kln (k)/kwith a nonvanishing probability. On the basis of deep but nonrigorous statistical mechanics ideas, a message passing algorithm calledBelief Propagation Guided Decimationhas been put forward (Mézard, Parisi, Zecchina: Science 2002; Braunstein, Mézard, Zecchina: Random Struc. Algorithm 2005). Experiments suggested that the algorithm might succeed for densities very close tork− SATfork= 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of this algorithm on a nontrivial input distribution, in the present article we show that Belief Propagation Guided Decimation fails to solve randomk-SAT formulas already form/n=O(2k/k), almost a factor ofkbelow the satisfiability thresholdrk− SAT. Indeed, the proof refutes a key hypothesis on which Belief Propagation Guided Decimation hinges for suchm/n.
登录
查看更多内容
随机 3-SAT 的最佳近视算法
DOI：
--
发表时间：
2000
期刊：
Proceedings 41st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
D. Achlioptas;G. Sorkin
通讯作者：
G. Sorkin
DOI：
--
发表时间：
2016
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
S. Hetterich
通讯作者：
S. Hetterich
计算随机 k-SAT 公式的正确真值分配
DOI：
--
发表时间：
2006
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
A. Montanari;Devavrat Shah
通讯作者：
Devavrat Shah
影响因子：
0.8
作者：
A. Montanari;R. Restrepo;P. Tetali
通讯作者：
P. Tetali
DPLL 的指数界限低于可满足性阈值
DOI：
--
发表时间：
2004
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
D. Achlioptas;P. Beame;Michael Molloy
通讯作者：
Michael Molloy