Satisfiability thresholds of random $k$-SAT

edit · history · discussion · files · long url · statistical mechanics probability theory

Numbers

$k$

$\alpha_s(k)$

4.26675 +/- 0.00015 †

comment: Mertens, Mézard and Zecchina give $\alpha_s(3)=4.26675\pm0.00015$ in Eq. (43), using the notation $\alpha_c$ for the satisfiability threshold [1].

9.931 †

21.117 †

43.37 †

87.79 †

Definition

Random $k$-SAT [5] is the satisfiability problem for a random $k$-CNF formula at clause density $\alpha=m/n$. The value $\alpha_s(k)$ is the one-step replica-symmetry-breaking cavity-method prediction for its satisfiability threshold [1].

Parameters

$k$

— clause length ($k\geq3$)

Formulas

(1)

The cavity-method prediction satisfies $\alpha_s(k)=2^k\log 2-\frac12(1+\log 2)+O(2^{-k})$ as $k\to\infty$ [1] [2].

Comments

(2)

In the model used by [1], the $m$ clauses are sampled independently; each clause uses $k$ distinct variables chosen uniformly, and each occurrence is negated with probability $\frac12$. The average literal degree is $k\alpha$.

(3)

Mertens, Mézard and Zecchina [1] write the satisfiability threshold as $\alpha_c$; their $\alpha_s$ is the stability limit of the 1RSB solution. This table follows the notation of Krzakala, Montanari, Ricci-Tersenghi, Semerjian and Zdeborová [2], where $\alpha_s(k)$ is the SAT-UNSAT threshold.

(4)

The listed values for $3\leq k\leq7$ are predictions of the cavity-method population-dynamics computation in [1]. Ding, Sly and Sun prove that, for all $k$ above some absolute constant $k_0$, the one-step replica-symmetry-breaking prediction gives the satisfiability threshold [3]; their theorem does not make $k_0$ explicit and does not certify any row listed here.

(5)

There is no $k=2$ row. The random $2$-SAT threshold is exactly $1$ [4]; this table records the 1RSB cavity-method values printed by [1], which start at $k=3$.

References

[1]

S. Mertens, M. Mézard and R. Zecchina, Threshold values of random K-SAT from the cavity method, Random Structures & Algorithms 28 (2006), 340-373. (arXiv) (doi)

[2]

F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proceedings of the National Academy of Sciences of the United States of America 104 (2007), 10318-10323. (arXiv) (doi)

[3]

J. Ding, A. Sly and N. Sun, Proof of the satisfiability conjecture for large $k$, Annals of Mathematics 196 (2022), 1-388. (arXiv)

[4]

V. Chvátal and B. Reed, Mick gets some (the odds are on his side) (satisfiability), Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992, 620-627. (doi)

Links

[5]

Wikipedia: Boolean satisfiability problem

Similar tables

satisfiability thresholds of random $k$-XORSAT — the XOR analogue, where the threshold is proven and computed from a scalar root equation

core thresholds of random $k$-uniform hypergraphs — twice the $2$-core threshold $c_{k,2}$ is the clause density at which the pure literal rule stops solving random $k$-SAT

Data properties

Entries are of type: real number

How well the digits are known: heuristic

Sources of data: [1], [2], [3]

Table is complete: no (it holds the cavity-method values printed by Mertens, Mézard and Zecchina for every $k$ with $3\leq k\leq7$)

How they were obtained:

The values are transcribed from Table 1 and Eq. (43) of [1]. The $k=3$ entry stores the centre $4.26675$ with the published $2\sigma$ radius $0.00015$.

For $4\leq k\leq7$, [1] prints the decimal values without separate error bars, so each entry is stored as the printed decimal and carries the database interval implied by its last digit. Before any entry was written, the rows $k=4,5,6$ were compared with the rounded values $9.93$, $21.12$ and $43.4$ in Table 1 of [2], and all rows were compared with the large-$k$ asymptotic in (1). That comparison checks the convention and scale; it is not an error bound. No rigorous proof is known for the listed small values.