论文标题
随机2-SAT分区功能
The random 2-SAT partition function
论文作者
论文摘要
我们表明，在整个令人满意的阶段中，随机$ 2 $ -SAT公式的满足分配数量的概率收敛于统计物理学的腔体方法预测的表达式。证明是基于表明信念传播算法的正确边缘概率，即在统一的随机满足分配下，变量设置为“ true”。
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random $2$-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to `true' under a uniformly random satisfying assignment.
