For random K-SAT — a Boolean formula in conjunctive normal form with n variables and m clauses, each the OR of K randomly chosen literals — experiments since the 1990s show a sharp satisfiability transition as the clause density alpha = m/n grows. Determining the exact threshold in the thermodynamic limit is the satisfiability conjecture, posed as an open problem by Krzakala, Mézard and Zdeborová in their study of reweighted belief propagation and quiet planting (JSAT, 2014), which tabulated threshold values only as non-rigorous cavity-method predictions. The conjecture is now a theorem for clause sizes K exceeding some large undetermined constant (Ding–Sly–Sun; Coja-Oghlan–Panagiotou), but for every fixed small K, in particular K = 3, it remains open: even the existence of a uniform, n-independent threshold location is unproven, and the best rigorous bounds for K = 3, namely 3.52 <= alpha_s <= 4.267 (the upper bound being the one-step replica symmetry breaking prediction itself), have stood for about two decades. The problem is to close this gap: prove or disprove, for the unresolved clause sizes, that a uniform threshold exists and determine its exact value.

Background

Random K-SAT is the canonical average-case model of constraint satisfaction. An instance is a conjunction of m clauses over n Boolean variables, each clause the disjunction (OR) of K literals (a variable or its negation) drawn uniformly at random; the clause density is the ratio alpha = m/n. Experiments in the 1990s found that as alpha crosses a critical value the probability that the formula is satisfiable drops sharply from asymptotically 1 to asymptotically 0 as n grows — an event of probability tending to 1 is said to happen with high probability (w.h.p.). Pinpointing this SAT/UNSAT threshold alpha_s(K) has become one of the benchmark open problems of probabilistic combinatorics and the theory of average-case complexity. The case K = 2 was settled in the early 1990s (alpha_s(2) = 1), but every K >= 3 presents genuine difficulty: Friedgut (1999) proved that a sharp threshold sequence alpha_s(K, n) exists, though possibly still depending on n, and whether the sequence converges to an n-independent limit is open for every fixed K below the large-K regime.

The most precise predictions come from statistical physics. The cavity method — a sophisticated but mathematically non-rigorous formalism for diluted disordered systems — and its one-step replica symmetry breaking (1RSB) refinement predict, for each K >= 3, a cascade of structural transitions in the set of solutions: at the clustering transition the solution set splits into exponentially many well-separated clusters; at the condensation transition almost all solutions collapse into a bounded number of clusters; and at the satisfiability threshold itself the last solutions disappear. The 1RSB analysis (Mertens, Mézard and Zecchina, 2006) predicts the threshold value alpha_s(K); for K = 3 the prediction is alpha_s(3) = 4.2667 approximately. On the rigorous side, the second moment method — bounding the probability of satisfiability through the first two moments of a well-chosen random variable counting satisfying assignments of a special type — yields lower bounds; analysis of greedy algorithms gives the best lower bound for K = 3, namely 3.52 (Hajiaghayi–Sorkin 2003; Kaporis, Kirousis and Lalas 2006). In the other direction, the interpolation method from mathematical physics (Franz and Leone 2003; Panchenko and Talagrand 2004) turns the 1RSB variational formula into a rigorous upper bound on the threshold, so for K = 3 the physics prediction 4.2667 is itself the best rigorous upper bound, up to its numerical evaluation.

The general conjecture was resolved for large clause sizes: Ding, Sly and Sun (Annals of Mathematics, 2022; preprint 2014) proved that for K exceeding some large absolute constant K_0 the threshold exists and equals the 1RSB prediction 2^K ln 2 - (1 + ln 2)/2 + o_K(1), and Coja-Oghlan and Panagiotou (Advances in Mathematics, 2016) independently proved the same asymptotic formula. Both proofs use the largeness of K critically (expansion and concentration properties of the random formula), and the asymmetry between the truth values of a Boolean variable — which has no analogue in symmetric problems such as random graph coloring or Not-All-Equal-SAT, where exact thresholds were obtained earlier — defeats the symmetry tricks that worked there. Consequently, for small K, and most prominently K = 3, the threshold remains undetermined: a summary of the state of the art co-authored by Coja-Oghlan in November 2025 states that for 3 <= K < K_0 even the existence of a uniform satisfiability threshold is open, and quotes the K = 3 bounds unchanged (lower bound 3.52, physics prediction about 4.267).

The source of the present problem statement sits squarely in the physics tradition. Krzakala, Mézard and Zdeborová (JSAT, 2014) introduced a reweighted partition function over the solutions of random K-SAT, studied it by belief propagation (an iterative message-passing algorithm for computing marginals on sparse factor graphs) and the cavity method, and used the resulting 'quiet planting' procedure — generating planted instances statistically indistinguishable from purely random ones below the condensation threshold — to exhibit purely entropic barriers between solution clusters and to build very hard satisfiable benchmarks. Their paper explicitly presents the tabulated satisfiability-threshold values as heuristic cavity predictions and its phase-transition picture, including the purely entropic barriers, as conjectures awaiting rigorous proof.

Problem Statement

Determine the exact location of the SAT/UNSAT threshold of random K-SAT in the thermodynamic limit for the clause sizes where it is still unresolved — every fixed K with 3 <= K below the large-K regime of Ding–Sly–Sun, most concretely K = 3. In the standard formulation: for a uniformly random K-CNF formula with n variables and clause density alpha, prove or disprove that there exists a clause density alpha_s(K), not depending on n, such that the formula is satisfiable with high probability when alpha < alpha_s(K) and unsatisfiable with high probability when alpha > alpha_s(K) as n tends to infinity; and determine the value of alpha_s(K). For K = 3 this amounts to deciding whether the one-step replica symmetry breaking (cavity-method) prediction for the threshold value, alpha_s(3) = 4.2667 approximately, is correct — that is, closing the gap between the best rigorous lower bound 3.52 (Kaporis–Kirousis–Lalas, Hajiaghayi–Sorkin) and the interpolation-method upper bound given by the 1RSB value itself — or establishing that no uniform threshold exists. Here the 1RSB prediction is the numeric clause-density value alpha_s(K) computed from the 1RSB cavity equations (Mertens–Mézard–Zecchina, 2006); the clustering and condensation transitions described in the Background concern the geometry of the solution set at clause densities below alpha_s(K) and are expository context rather than part of the proposition this task asks to settle. The question is resolved by settling the threshold for K = 3 alone, for a stated range of small K, or in general; the source (Krzakala–Mézard–Zdeborová, JSAT 2014) poses the question for random K-SAT generally, and the large-K case is already settled by Ding–Sly–Sun and Coja-Oghlan–Panagiotou.

References

  1. Florent Krzakala, Marc Mézard, Lenka Zdeborová, Reweighted Belief Propagation and Quiet Planting for Random K-SAT, Journal on Satisfiability, Boolean Modeling and Computation 8(3-4):149-171 (2014). DOI: 10.3233/sat190096, https://doi.org/10.3233/sat190096 (preprint: arXiv:1203.5521)
  2. Jian Ding, Allan Sly, Nike Sun, Proof of the satisfiability conjecture for large k, Annals of Mathematics 196(1):1-388 (2022). DOI: 10.4007/annals.2022.196.1.1, https://doi.org/10.4007/annals.2022.196.1.1 (preprint: arXiv:1411.0650)
  3. Amin Coja-Oghlan, Konstantinos Panagiotou, The asymptotic k-SAT threshold, Advances in Mathematics 288:985-1068 (2016). DOI: 10.1016/j.aim.2015.11.007, https://doi.org/10.1016/j.aim.2015.11.007 (preprint: arXiv:1310.2728)
  4. Stephan Mertens, Marc Mézard, Riccardo Zecchina, Threshold values of random K-SAT from the cavity method, Random Structures & Algorithms 28(3):340-373 (2006). DOI: 10.1002/rsa.20090, https://doi.org/10.1002/rsa.20090
  5. Ehud Friedgut, appendix by Jean Bourgain, Sharp thresholds of graph properties, and the k-sat problem, Journal of the American Mathematical Society 12(4):1017-1054 (1999). DOI: 10.1090/S0894-0347-99-00305-7, https://doi.org/10.1090/S0894-0347-99-00305-7
  6. Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas, The probabilistic analysis of a greedy satisfiability algorithm, Random Structures & Algorithms 28(4):444-480 (2006). DOI: 10.1002/rsa.20104, https://doi.org/10.1002/rsa.20104
  7. MohammadTaghi Hajiaghayi, Gregory B. Sorkin, The Satisfiability Threshold of Random 3-SAT Is at Least 3.52 (2003). arXiv:math/0310193, https://arxiv.org/abs/math/0310193 (IBM Research Report RC22942)
  8. Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill, Vincent Pfenninger, Maurice Rolvien, Pavel Zakharov, Kostas Zampetakis, The random k-SAT Gibbs uniqueness threshold revisited (2025). arXiv:2506.01359, https://arxiv.org/abs/2506.01359
  9. Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, Yitong Yin, Counting random k-SAT near the satisfiability threshold (2024). arXiv:2411.02980, https://arxiv.org/abs/2411.02980
  10. P. H. Lundow, K. Markström, Revisiting the cavity-method threshold for random 3-SAT, Physical Review E 99:022106 (2019). DOI: 10.1103/physreve.99.022106, https://doi.org/10.1103/physreve.99.022106
  11. Vitaly Feldman, Will Perkins, Santosh Vempala, On the Complexity of Random Satisfiability Problems with Planted Solutions, SIAM Journal on Computing 47(4):1294-1338 (2018). DOI: 10.1137/16m1078471, https://doi.org/10.1137/16m1078471 (preprint: arXiv:1311.4821)
  12. Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski, Quiet Planting for k-SAT, Multiple Solutions of Arbitrary Geometry (2026). arXiv:2606.15979, https://arxiv.org/abs/2606.15979
  13. Matteo Bellitti, Federico Ricci-Tersenghi, Antonello Scardicchio, Entropic barriers as a reason for hardness in both classical and quantum algorithms (2021). arXiv:2102.00182, https://arxiv.org/abs/2102.00182
  14. Silvio Franz, Michele Leone, Replica Bounds for Optimization Problems and Diluted Spin Systems, Journal of Statistical Physics 111(3-4):535-564 (2003). DOI: 10.1023/a:1022885828956, https://doi.org/10.1023/a:1022885828956
  15. Dmitry Panchenko, Michel Talagrand, Bounds for diluted mean-fields spin glass models, Probability Theory and Related Fields 130(3):319-336 (2004). DOI: 10.1007/s00440-004-0342-2, https://doi.org/10.1007/s00440-004-0342-2