Raymond Jack, Sportiello Andrea, Zdeborová Lenka
NCRG, Aston University, Aston Triangle, Birmingham B4 7EJ, United Kingdom.
Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Jul;76(1 Pt 1):011101. doi: 10.1103/PhysRevE.76.011101. Epub 2007 Jul 2.
We study typical case properties of the 1-in-3 satisfiability problem, the Boolean satisfaction problem, where a clause is satisfied by exactly one literal, in an enlarged random ensemble parametrized by average connectivity and probability of negation of a variable in a clause. Random 1-in-3 satisfiability and exact 3-cover are special cases of this ensemble. We interpolate between these cases from a region where satisfiability can be typically decided for all connectivities in polynomial time to a region where deciding satisfiability is hard, in some interval of connectivities. We derive several rigorous results in the first region and develop a one-step replica-symmetry-breaking cavity analysis in the second one. We discuss the prediction for the transition between the almost surely satisfiable and the almost surely unsatisfiable phase, and other structural properties of the phase diagram, in light of cavity method results.
我们研究三分之一可满足性问题（一种布尔可满足性问题，其中一个子句恰好由一个文字满足）在由平均连通性和子句中变量否定概率参数化的扩大随机系综中的典型案例性质。随机三分之一可满足性和精确三覆盖是该系综的特殊情况。我们在这些情况之间进行插值，从一个对于所有连通性都可以在多项式时间内典型地判定可满足性的区域，到一个在某些连通性区间内判定可满足性很难的区域。我们在第一个区域推导出几个严格的结果，并在第二个区域发展了一步复制对称破缺腔分析。根据腔方法的结果，我们讨论了几乎肯定可满足和几乎肯定不可满足相之间转变的预测以及相图的其他结构性质。
