Leuzzi and Parisi (2001) computed the thermodynamics of random 3-SAT in the infinite-connectivity limit, scaling the inverse temperature as β=μ/α\beta=\mu/\sqrt{\alpha} and the energy as e(μ,α)=(E−α/8)/αe(\mu,\alpha)=(E-\alpha/8)/\sqrt{\alpha}, and found evidence that the UNSAT phase breaks replica symmetry continuously. Much of that program has since been completed: the full-RSB solution was constructed and solved numerically down to zero temperature (Crisanti-Leuzzi-Parisi 2002), the leading-order ground-state formula was proven rigorously by Panchenko through the zero-temperature Parisi formula of the mixed pp-spin model with covariance ξ(x)=(1+x)K−1\xi(x)=(1+x)^K-1, and the infinite-step nature of the zero-temperature Parisi measure was proven in general. The surviving open problem is the controlled extension to finite clause density: the subleading terms of the 1/α1/\sqrt{\alpha} expansion of the ground-state energy beyond the proven leading order, the construction and solution of the finite-connectivity full-RSB (Gardner) regime above the 1RSB instability at αG≈4.39\alpha_G\approx 4.39 in 3-SAT, and the quantitative reconciliation of the asymptotic threshold estimate αc≈(8e0)2≈7.11\alpha_c\approx(8e_0)^2\approx 7.11 with the 1RSB threshold αc≈4.267\alpha_c\approx 4.267.

Background

Random KK-SAT is the canonical random constraint satisfaction problem: NN Boolean variables and αN\alpha N random clauses, each clause the logical OR of KK randomly chosen literals (a variable or its negation), so that the clause density α\alpha is the ratio of clauses to variables. Mapping truth assignments to Ising spins σi=±1\sigma_i=\pm 1 turns a formula into a Hamiltonian H(σ)H(\sigma) that counts unsatisfied clauses; a formula is satisfiable iff min⁡σH=0\min_\sigma H=0. Numerical experiments by Kirkpatrick and Selman (1994) found a sharp SAT/UNSAT threshold αc≈4.2\alpha_c\approx 4.2 for K=3K=3: below it a satisfying assignment almost surely exists, above it none does, and in the UNSAT phase the central object is the ground-state energy density — the minimum number of violated clauses per variable, averaged over the random ensemble of formulas (a quenched average) in the thermodynamic limit N→∞N\to\infty.

The replica method of disordered-systems physics computes such quenched averages from the analytic continuation of Zn‾\overline{Z^n} to n→0n\to 0. Its key structural question is replica symmetry breaking (RSB): whether the low-temperature Gibbs measure splits into many pure states, and in what pattern. In one-step RSB (1RSB) the states form an exponential number of essentially uncorrelated clusters; in continuous or full RSB (FRSB, also called ∞\infty-RSB) the states organize into an infinite hierarchy described by a Parisi order parameter function q(x)q(x) on x∈[0,1]x\in[0,1] — the structure of the Sherrington-Kirkpatrick (SK) model, the prototypical fully connected (mean-field) spin glass. Whether 1RSB suffices or further breaking occurs is decided by stability (Gardner-type) analysis of the 1RSB solution; a continuous instability of 1RSB toward FRSB is called a Gardner transition.

Leuzzi and Parisi (2001) analyzed 3-SAT in the infinite-connectivity limit α→∞\alpha\to\infty, scaling the inverse temperature as β=μ/α\beta=\mu/\sqrt{\alpha} and the energy as e(μ,α)=(E−α/8)/αe(\mu,\alpha)=(E-\alpha/8)/\sqrt{\alpha} (a random assignment violates a fraction 2−K=1/82^{-K}=1/8 of clauses). In this limit the problem becomes a fully connected mixed pp-spin model — a Gaussian spin Hamiltonian whose covariance is a fixed mixture of powers of the spin overlap — with mixture ξ(x)=(1+x)3−1\xi(x)=(1+x)^3-1. They found a replica-symmetric-to-RSB transition at τc=1/μc=0.21978\tau_c=1/\mu_c=0.21978, and one- and two-step RSB solutions whose thermodynamic pathologies (e.g. negative low-temperature entropy) shrink at each step, pointing to continuous RSB. At zero temperature the rescaled energy e(μ,α)e(\mu,\alpha) is nonpositive, since the ground state satisfies E0≤α/8E_0\le\alpha/8; writing e0≡−lim⁡μ→∞e(μ,α)=c∗/8≈0.3334e_0\equiv-\lim_{\mu\to\infty}e(\mu,\alpha)=c_*/8\approx 0.3334 (two-step extrapolation) for its magnitude, the leading-order threshold estimate is αc≈(8e0)2≈7.11\alpha_c\approx(8e_0)^2\approx 7.11. Two issues were left open: the assumed free interchange of the α→∞\alpha\to\infty and zero-temperature (μ→∞\mu\to\infty) limits, and the extent to which the asymptotic, continuously broken structure describes finite α\alpha down to the threshold region.

Later work resolved the α→∞\alpha\to\infty core and reshaped the finite-α\alpha question. Crisanti, Leuzzi and Parisi (2002) derived the full ∞\infty-RSB equations for a class containing the over-constrained 3-SAT model and solved them numerically to T=0T=0: the UNSAT phase is ∞\infty-RSB (like the SK model in a magnetic field), giving e0e_0 through a variational principle and αc≤7.10969\alpha_c\le 7.10969. Panchenko (2018) proved rigorously that the minimum fraction of unsatisfied clauses is α/2K−α c∗(N)/2K+o(α)\alpha/2^K-\sqrt{\alpha}\,c_*(N)/2^K+o(\sqrt{\alpha}) as α→∞\alpha\to\infty, uniformly in NN, where c∗c_* is the normalized maximum energy of that mixed pp-spin model, computable by the zero-temperature Parisi formula of Auffinger and Chen — establishing the Leuzzi-Parisi formula; Auffinger, Chen and Zeng (2020) proved that the zero-temperature Parisi measure of any mixed pp-spin model has infinitely many support points. Meanwhile, threshold-scale physics is 1RSB: the cavity method (a message-passing technique for sparse systems) and survey propagation (a message-passing algorithm for random satisfiability built on the one-step-RSB cavity formalism) (Mézard-Parisi-Zecchina 2002; Mertens-Mézard-Zecchina 2006) give αc≈4.267\alpha_c\approx 4.267 with a stable 1RSB solution, and Montanari, Parisi and Ricci-Tersenghi (2004) showed for 3-SAT that 1RSB is stable only in a window: it is unstable in the underconstrained SAT region below αm≈4.153\alpha_m\approx 4.153 and, crucially, in the UNSAT phase the 1RSB ground state is unstable beyond a Gardner transition at αG=4.390(5)\alpha_G=4.390(5), above which 1RSB provides only a lower bound on the ground-state energy. Rigorous counterparts exist at leading order (Sen 2018 for sparse hypergraph optimization; Bartha-Sun-Zhang 2019 for 1RSB breakdown in regular NAE-SAT; Ding-Sly-Sun 2022 proving the satisfiability threshold for large KK). What no work supplies is the quantitative bridge between the exactly characterized α→∞\alpha\to\infty limit and finite clause density.

Problem Statement

Develop the quantitative zero-temperature theory of the UNSAT phase of random 3-SAT (KK-SAT with K=3K=3) at finite clause density, connecting the exactly characterized full-connectivity limit to the threshold scale. The target instance is K=3K=3; the general-K≥3K\ge 3 case is the direct generalization and follows from the same equations. Determine the thermodynamic-limit ground-state energy density E0(α)E_0(\alpha) and the structure of the replica-symmetry-breaking order parameter describing the ground states over the whole UNSAT phase α>αc≈4.267\alpha>\alpha_c\approx 4.267, with controlled errors: in the stable-1RSB window αc<α<αG≈4.39\alpha_c<\alpha<\alpha_G\approx 4.39 both are already fixed by the stable 1RSB solution, while the new work is required in the large-α\alpha limit and above the Gardner transition α>αG\alpha>\alpha_G, the two ends being reconciled. The three items below are logically linked: the finite-α\alpha results must be consistent with the large-α\alpha expansion in item 1 and must satisfy the consistency conditions of item 3. Concretely, this requires:

  1. Subleading asymptotics. Compute the terms of the large-α\alpha expansion of E0(α)E_0(\alpha) beyond the proven leading order E0(α)=α/8−α c∗/8+o(α)E_0(\alpha)=\alpha/8-\sqrt{\alpha}\,c_*/8+o(\sqrt{\alpha}), where c∗c_* is the normalized maximum energy of the fully connected mixed pp-spin model with mixture ξ(x)=(1+x)K−1\xi(x)=(1+x)^K-1 — an expansion in powers of 1/α1/\sqrt{\alpha} — or prove rigorous error bounds on the remainder that are effective at explicit, moderate values of α\alpha (the present rigorous remainder O(α1/3)O(\alpha^{1/3}) is guaranteed smaller than the leading correction only for astronomically large α\alpha).

  2. The finite-connectivity Gardner regime. Above the Gardner instability αG≈4.39\alpha_G\approx 4.39 of 3-SAT, where the one-step replica symmetry breaking (1RSB) ground-state description is unstable and yields only a lower bound, construct and solve the finite-connectivity full-RSB (continuous, infinite-step replica symmetry breaking) equations at zero temperature (or an equivalent variational or cavity formulation), yielding the RSB order parameter and ground-state energy as functions of α\alpha.

  3. Consistency of the two ends. The finite-α\alpha solution must match the known limits: its rescaled ground-state energy (E0(α)−α/8)/α(E_0(\alpha)-\alpha/8)/\sqrt{\alpha} tends to the zero-temperature Parisi value −e0=−c∗/8-e_0=-c_*/8 of the limiting mixed pp-spin model as α→∞\alpha\to\infty, reproduces the 1RSB ground-state energy as α↓αG\alpha\downarrow\alpha_G, and the discrepancy between the asymptotic threshold estimate αc≈(8e0)2≈7.11\alpha_c\approx(8e_0)^2\approx 7.11 and the 1RSB threshold αc≈4.267\alpha_c\approx 4.267 must be resolved quantitatively, i.e. the clause density above which the asymptotic expansion becomes reliable, and whether it can be meaningfully evaluated at threshold scale, must be determined.

References

  1. L. Leuzzi and G. Parisi, The K-SAT Problem in a Simple Limit, Journal of Statistical Physics 103, 679-695 (2001). DOI: 10.1023/A:1010388300998, https://doi.org/10.1023/A:1010388300998 (preprint: arXiv:cond-mat/0007364, https://arxiv.org/abs/cond-mat/0007364)
  2. A. Crisanti, L. Leuzzi and G. Parisi, The 3-SAT problem with large number of clauses in the ∞\infty-replica symmetry breaking scheme, Journal of Physics A: Mathematical and General 35, 481-497 (2002). DOI: 10.1088/0305-4470/35/3/303, https://doi.org/10.1088/0305-4470/35/3/303 (preprint: arXiv:cond-mat/0108433, https://arxiv.org/abs/cond-mat/0108433)
  3. A. Montanari, G. Parisi and F. Ricci-Tersenghi, Instability of one-step replica-symmetry-broken phase in satisfiability problems, J. Phys. A: Math. Gen. 37, 2073 (2004). DOI: 10.1088/0305-4470/37/6/008, https://doi.org/10.1088/0305-4470/37/6/008 (preprint: arXiv:cond-mat/0308147, https://arxiv.org/abs/cond-mat/0308147)
  4. S. Mertens, M. Mézard and R. Zecchina, Threshold values of random K-SAT from the cavity method, Random Structures and Algorithms 28, 340-373 (2006). DOI: 10.1002/rsa.20090, https://doi.org/10.1002/rsa.20090 (preprint: arXiv:cs/0309020, https://arxiv.org/abs/cs/0309020)
  5. M. Mézard, G. Parisi and R. Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems, Science 297, 812-815 (2002). DOI: 10.1126/science.1073287, https://doi.org/10.1126/science.1073287
  6. S. Kirkpatrick and B. Selman, Critical Behavior in the Satisfiability of Random Boolean Expressions, Science 264, 1297 (1994). DOI: 10.1126/science.264.5163.1297, https://doi.org/10.1126/science.264.5163.1297
  7. D. Panchenko, On the K-sat model with large number of clauses, Random Structures and Algorithms 52, no. 3, 536-542 (2018). DOI: 10.1002/rsa.20748, https://doi.org/10.1002/rsa.20748 (preprint: arXiv:1608.06256, https://arxiv.org/abs/1608.06256)
  8. A. Auffinger and W.-K. Chen, Parisi formula for the ground state energy in the mixed pp-spin model, Annals of Probability 45, no. 6B (2017). DOI: 10.1214/16-aop1173, https://doi.org/10.1214/16-aop1173 (preprint: arXiv:1606.05335, https://arxiv.org/abs/1606.05335)
  9. A. Auffinger, W.-K. Chen and Q. Zeng, The SK model is infinite step replica symmetry breaking at zero temperature, Communications in Pure and Applied Mathematics 73, 921-943 (2020). DOI: 10.1002/cpa.21886, https://doi.org/10.1002/cpa.21886 (preprint: arXiv:1703.06872, https://arxiv.org/abs/1703.06872)
  10. J. Ding, A. Sly and N. Sun, Proof of the satisfiability conjecture for large k, Annals of Mathematics 196, no. 1 (2022). DOI: 10.4007/annals.2022.196.1.1, https://doi.org/10.4007/annals.2022.196.1.1 (preprint: arXiv:1411.0650, https://arxiv.org/abs/1411.0650)
  11. Z. Bartha, N. Sun and Y. Zhang, Breaking of 1RSB in Random Regular MAX-NAE-SAT, Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019). DOI: 10.1109/FOCS.2019.00086, https://doi.org/10.1109/FOCS.2019.00086 (preprint: arXiv:1904.08891, https://arxiv.org/abs/1904.08891, posted under the title 'Breaking of 1RSB in random MAX-NAE-SAT')
  12. S. Sen, Optimization on sparse random hypergraphs and spin glasses, Random Structures and Algorithms (2018). DOI: 10.1002/rsa.20774, https://doi.org/10.1002/rsa.20774 (preprint: arXiv:1606.02365, https://arxiv.org/abs/1606.02365)
  13. H. Zhou, T→0T\to 0 mean-field population dynamics approach for the random 3-satisfiability problem, Physical Review E 77, 066102 (2008). DOI: 10.1103/PhysRevE.77.066102, https://doi.org/10.1103/PhysRevE.77.066102 (preprint: arXiv:0801.0205, https://arxiv.org/abs/0801.0205)
  14. G. Parisi, The Marginally Stable Bethe Lattice Spin Glass Revisited, Journal of Statistical Physics 167, 515-542 (2017). DOI: 10.1007/s10955-017-1724-z, https://doi.org/10.1007/s10955-017-1724-z (preprint: arXiv:1609.05327, https://arxiv.org/abs/1609.05327)
  15. F. Concetti, The Full Replica Symmetry Breaking in the Ising Spin Glass on Random Regular Graph, Journal of Statistical Physics 173, 1459-1483 (2018). DOI: 10.1007/s10955-018-2142-6, https://doi.org/10.1007/s10955-018-2142-6 (preprint: arXiv:1712.00367, https://arxiv.org/abs/1712.00367)
  16. G. Boschi and G. Parisi, Free energy expansion of the spin glass with finite connectivity for ∞\infty RSB, arXiv:2001.01966 (2020), https://arxiv.org/abs/2001.01966
  17. C. Angelini, G. Parisi and F. Ricci-Tersenghi, One-loop topological expansion for spin glasses in the large connectivity limit, EPL 121, 27001 (2018). DOI: 10.1209/0295-5075/121/27001, https://doi.org/10.1209/0295-5075/121/27001