Krishnamurthy Supriya
Department of Physics, Stockholm University, SE 106 91, Stockholm, Sweden.
National Institute of Science Education and Research, PO Bhimpur-Padanpur, Via Jatni, Khurda-Bhubaneswar, Orissa 752050, India.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Oct;92(4):042144. doi: 10.1103/PhysRevE.92.042144. Epub 2015 Oct 21.
The satisfiability threshold for constraint satisfaction problems is that value of the ratio of constraints (or clauses) to variables, above which the probability that a random instance of the problem has a solution is zero in the large system limit. Two different approaches to obtaining this threshold have been discussed in the literature: using first or second moment methods which give rigorous bounds or using the nonrigorous but powerful replica-symmetry-breaking (RSB) approach, which gives very accurate predictions on random graphs. In this paper, we lay out a different route to obtaining this threshold on a Bethe lattice. We need make no assumptions about the solution-space structure, a key assumption in the RSB approach. Despite this, our expressions and threshold values exactly match the best predictions of the cavity method under the one-step RSB hypothesis. In addition we can use the same procedure to obtain other useful quantities on the Bethe lattice such as the second moment of the number of solutions. Our method hence provides alternate interpretations as well as motivations for the key equations in the RSB approach.
约束满足问题的可满足性阈值是指约束（或子句）与变量的比率值，在大系统极限情况下，高于该值时问题的随机实例有解的概率为零。文献中讨论了两种获得该阈值的不同方法：使用给出严格界限的一阶或二阶矩方法，或使用虽不严格但强大的复制对称破缺（RSB）方法，该方法能对随机图给出非常准确的预测。在本文中，我们阐述了一种在贝叶斯晶格上获得该阈值的不同途径。我们无需对解空间结构做任何假设，而这是RSB方法中的一个关键假设。尽管如此，我们的表达式和阈值在一步RSB假设下与腔方法的最佳预测完全匹配。此外，我们可以使用相同的程序在贝叶斯晶格上获得其他有用的量，比如解的数量的二阶矩。因此，我们的方法为RSB方法中的关键方程提供了替代解释以及动机。
