Franz S, Leone M, Ricci-Tersenghi F, Zecchina R
ICTP, Condensed Matter Group, P.O. Box 586, I-34014 Trieste, Italy.
Phys Rev Lett. 2001 Sep 17;87(12):127209. doi: 10.1103/PhysRevLett.87.127209. Epub 2001 Aug 31.
We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma(d) = 0.818, and gamma(s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( gamma(var)(c) = 4.396 and gamma(var)(c) = 2.149).
我们研究了具有有限连通性的 p 自旋玻璃模型的低温特性以及一些优化问题。使用一步函数副本对称破缺假设，我们可以精确求解具有均匀连通性的图的鞍点方程。所得的基态能量与数值模拟完全一致。对于连通性波动的图，相同的假设可以变分的方式使用：对于 p 自旋模型（在计算机科学中称为 p - XOR - SAT），它提供了精确的构型熵以及动态和静态临界连通性（对于 p = 3，γ(d) = 0.818，γ(s) = 0.918），而对于像 3 - SAT 或双色问题这样的硬优化问题，它为其临界阈值提供了新的上界（γ(var)(c) = 4.396 和 γ(var)(c) = 2.149）。
