论文标题
在随机$ k $ -sat模型上的信念传播
Belief Propagation on the random $k$-SAT model
论文作者
论文摘要
通过统计物理学来证实预测，我们证明，信念传播消息传递算法近似于所有条款/可变密度的随机$ k $ -sAT模型的分区函数，并且满足了远距离相关条件的适度缺乏。该条件在物理语言中被称为“复制对称性”。从此结果，我们推断出复制对称性断裂相变发生在低温下的$ k $ -sat模型中，对于以下的子句/可变密度，但接近满足性阈值。
Corroborating a prediction from statistical physics, we prove that the Belief Propagation message passing algorithm approximates the partition function of the random $k$-SAT model well for all clause/variable densities and all inverse temperatures for which a modest absence of long-range correlations condition is satisfied. This condition is known as "replica symmetry" in physics language. From this result we deduce that a replica symmetry breaking phase transition occurs in the random $k$-SAT model at low temperature for clause/variable densities below but close to the satisfiability threshold.
