Abstract
Since the early 2000s physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mézard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k -SAT problem is , with limk→∞εk=0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture.
MSC
- 60C05;
- 05C80
Keywords
- Phase transitions;
- Satisfiability problem;
- Probabilistic combinatorics
1. Introduction
For integers k≥3,N,M>0 choose a Boolean formula Φ=Φk(N,M)=Φ1∧⋯∧ΦM in conjunctive normal form with clauses Φi=Φi1∨⋯∨Φik, Φij∈{x1,¬x1,…,xN,¬xN} uniformly at random out of all (2N)kM possible such formulas. Since the early 1990s experimental work has supported the hypothesis that for any k≥3 there is a sharp threshold for satisfiability [8] and [30]. That is, there exists a number rk-SAT>0 such that as the formula for density M/N passes rk-SAT, the probability of that the random formula Φ is satisfiable drops from asymptotically 1 to asymptotically 0 as N→∞. An impressive bulk of theoretical work has since been devoted to establishing the existence and location of this threshold rk-SAT as well as the existence of similar “satisfiability thresholds” in other random constraint satisfaction problems (see, e.g., [3] and the references therein). In fact, pinning the satisfiability threshold rk-SAT has become one of the best-known benchmark problems in probabilistic combinatorics.
From its early days the random k-SAT problem has drawn the attention of statistical physicists. Through the physics lens, random k-SAT is an example of a “disordered system”. Over the past decades, physicists have developed a systematic albeit non-rigorous approach to this type of problem called the cavity method [36]. More specifically, the so-called 1-step replica symmetry breaking (“1RSB”) installment of the cavity method, which is centered around the Survey Propagation message passing procedure [37], predicts that [35]
From the viewpoint of the cavity method as well as from a rigorous perspective, random k-SAT is by far the most challenging problem among the standard examples of random CSPs. The reason is that there is a fundamental asymmetry between the role that the Boolean values ‘true’ and ‘false’ play. More specifically, consider the thought experiment of first generating a random formula Φ and then sampling a random satisfying assignment σ of Φ. Then the local “shape” of Φ provides significant clues as to the probability that a given variable x takes the value ‘true’ under the random assignment σ. For instance, if x appears many more times positively than negatively in Φ, then we should expect that the probability that x takes the value ‘true’ under σ is greater than 1/2. This is in contrast to, e.g., the graph coloring problem, where all the colors have the same “meaning”. In fact, the probability that a given vertex takes a particular color in a random coloring is just uniform, simply because we can permute the color classes. Similarly, the k-NAESAT (“Not-All-Equal-Satisfiability”) problem, which asks for a satisfying assignment whose inverse assignment is also satisfying, is perfectly symmetric by its very definition. 1