Analysing Survey Propagation Guided Decimation on Random Formulas
Analysing Survey Propagation Guided Decimation on Random Formulas
复制标题
分析随机公式的调查传播引导抽取
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Hetterich
中科院分区：
文献类型：
--
作者：
S. Hetterich
设$\varPhi$是一个具有$n$个变量和$m$个子句的均匀分布的随机$k$-SAT公式。对于子句/变量比$m/n \leq r_{k\text{-SAT}} \sim 2^k\ln2$，公式$\varPhi$以高概率满足。然而，没有有效的算法是已知的可证明找到一个令人满意的分配超过$m/n \sim 2k \ln（k）/k$与非零概率。对$k$-CNF的非严格统计力学工作导致了一种新的高效“消息传递算法”的开发，称为\n {Survey Propagation Guided Decimation} [M\'ezard et al.，Science 2002]。针对k= 3，4，5 $的实验表明，该算法能够找到接近r_{k\text{-SAT}}$的满意赋值。然而，在本文中，我们证明了调查传播引导抽取的基本版本无法有效地解决随机$k$-SAT公式已经为$m/n=2^k（1+\vareps_k）\ln（k）/k$与$\lim_{k\to\infty}\vareps_k= 0$几乎是一个因子$k$低于$r_{k\text{-SAT}}$。
Let $\varPhi$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. For clauses/variables ratio $m/n \leq r_{k\text{-SAT}} \sim 2^k\ln2$ the formula $\varPhi$ is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond $m/n \sim 2k \ln(k)/k$ with a non-vanishing probability. Non-rigorous statistical mechanics work on $k$-CNF led to the development of a new efficient "message passing algorithm" called \emph{Survey Propagation Guided Decimation} [M\'ezard et al., Science 2002]. Experiments conducted for $k=3,4,5$ suggest that the algorithm finds satisfying assignments close to $r_{k\text{-SAT}}$. However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random $k$-SAT formulas efficiently already for $m/n=2^k(1+\varepsilon_k)\ln(k)/k$ with $\lim_{k\to\infty}\varepsilon_k= 0$ almost a factor $k$ below $r_{k\text{-SAT}}$.