Counting good truth assignments of random k-SAT formulae
Counting good truth assignments of random k-SAT formulae
复制标题
计算随机 k-SAT 公式的正确真值分配
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Devavrat Shah
中科院分区：
文献类型：
--
作者：
A. Montanari;Devavrat Shah
我们提出了一种确定性近似算法，用于在多项式时间内计算随机<i>k</i>-可满足性（<i>k</i>-SAT）公式的“好”真值分配数的<i>对数</i>（“好”是指违反了一小部分子句）。只要子句密度（子句与变量的比率）α< α<inf>u</inf>(<i>k</i>) = 2<i>k</i><sup>-1</sup>log<i>k</i>(1 + <i>o</i>(1))，相对误差就由一个任意小的常数ε限定在上面，概率为<sup> </sup>。该算法通过信念传播计算边际分布，并使用插值过程。该方案替代了传统的基于边际概率的MCMC逼近方案，并结合自约法，该方案不容易推广到目前的问题。
We present a deterministic approximation algorithm to compute <i>logarithm</i> of the number of 'good' truth assignments for a random <i>k</i>-satisfiability (<i>k</i>-SAT) formula in polynomial time (by 'good' we mean that violates a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant ε with high probability<sup>1</sup> as long as the clause density (ratio of clauses to variables) α < α<inf>u</inf>(<i>k</i>) = 2<i>k</i><sup>-1</sup>log<i>k</i>(1 + <i>o</i>(1)). The algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. This scheme substitutes the traditional one based on approximation of marginal probabilities via MCMC, in conjunction with self-reduction, which is not easy to extend to the present problem.
Our results are expected hold for a reasonable non-random setup with locally tree-like sparse <i>k</i>-SAT formulas. We derive 2<i>k</i><sup>-1</sup> log <i>k</i>(1+<i>o</i>(1)) as threshold for uniqueness of the Gibbs distribution on satisfying assignment of random infinite tree <i>k</i>-SAT formulae to establish our results, which is of interest in its own right.