The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

Achlioptas, Dimitris ¹   ; Peres, Yuval ²

¹ Microsoft Research, One Microsoft Way, Redmond, Washington 98052
² Department of Statistics, University of California, Berkeley, California 94720

Journal of the American Mathematical Society, Tome 17 (2004) no. 4, pp. 947-973

Résumé

Let $F_k(n,m)$ be a random $k$-CNF formula formed by selecting uniformly and independently $m$ out of all possible $k$-clauses on $n$ variables. It is well known that if $r \geq 2^k \log 2$, then $F_k(n,rn)$ is unsatisfiable with probability that tends to 1 as $n \to \infty$. We prove that if $r \leq 2^k \log 2 - t_k$, where $t_k = O(k)$, then $F_k(n,rn)$ is satisfiable with probability that tends to 1 as $n \to \infty$. Our technique, in fact, yields an explicit lower bound for the random $k$-SAT threshold for every $k$. For $k \geq 4$ our bounds improve all previously known such bounds.

Détail

DOI : 10.1090/S0894-0347-04-00464-3

Bibliographie

[1] Chao, Ming-Te, Franco, John Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the 𝑘-satisfiability problem Inform. Sci. 1990 289 314

[2] De Bruijn, N. G. Asymptotic methods in analysis 1981

[3] Dembo, Amir, Peres, Yuval, Rosen, Jay, Zeitouni, Ofer Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk Acta Math. 2001 239 270

[4] Dembo, Amir, Zeitouni, Ofer Large deviations techniques and applications 1998

[5] Dubois, O., Boufkhad, Y. A general upper bound for the satisfiability threshold of random 𝑟-SAT formulae J. Algorithms 1997 395 420

[6] Erdős, P., Lovász, L. Problems and results on 3-chromatic hypergraphs and some related questions 1975 609 627

[7] Erdős, P., Taylor, S. J. Some problems concerning the structure of random walk paths Acta Math. Acad. Sci. Hungar. 1960

[8] Franco, John, Paull, Marvin Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem Discrete Appl. Math. 1983 77 87

[9] Frieze, Alan, Suen, Stephen Analysis of two simple heuristics on a random instance of 𝑘-SAT J. Algorithms 1996 312 355

[10] Janson, Svante, Stamatiou, Yannis C., Vamvakari, Malvina Bounding the unsatisfiability threshold of random 3-SAT Random Structures Algorithms 2000 103 116

[11] Kirousis, Lefteris M., Kranakis, Evangelos, Krizanc, Danny, Stamatiou, Yannis C. Approximating the unsatisfiability threshold of random formulas Random Structures Algorithms 1998 253 269

[12] Monasson, Rémi, Zecchina, Riccardo Statistical mechanics of the random 𝐾-satisfiability model Phys. Rev. E (3) 1997 1357 1370