## The threshold for random $k$-SAT is $2^k\log 2-O(k)$

HTML articles powered by AMS MathViewer

- by Dimitris Achlioptas and Yuval Peres PDF
- J. Amer. Math. Soc.
**17**(2004), 947-973 Request permission

## Abstract:

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.## References

- naesat D. Achlioptas and C. Moore. The asymptotic order of the random $k$-SAT threshold. In
- Ming-Te Chao and John Franco,
*Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the $k$-satisfiability problem*, Inform. Sci.**51**(1990), no. 3, 289–314. MR**1072035**, DOI 10.1016/0020-0255(90)90030-E
cheese P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In - N. G. de Bruijn,
*Asymptotic methods in analysis*, 3rd ed., Dover Publications, Inc., New York, 1981. MR**671583** - Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni,
*Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk*, Acta Math.**186**(2001), no. 2, 239–270. MR**1846031**, DOI 10.1007/BF02401841 - Amir Dembo and Ofer Zeitouni,
*Large deviations techniques and applications*, 2nd ed., Applications of Mathematics (New York), vol. 38, Springer-Verlag, New York, 1998. MR**1619036**, DOI 10.1007/978-1-4612-5320-4 - O. Dubois and Y. Boufkhad,
*A general upper bound for the satisfiability threshold of random $r$-SAT formulae*, J. Algorithms**24**(1997), no. 2, 395–420. MR**1469655**, DOI 10.1006/jagm.1997.0867
dubannoun O. Dubois, Y. Boufkhad, and J. Mandler. Typical random 3-SAT formulae and the satisfiability threshold. In - P. Erdős and L. Lovász,
*Problems and results on $3$-chromatic hypergraphs and some related questions*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627. MR**0382050** - P. Erdős and S. J. Taylor,
*Some problems concerning the structure of random walk paths*, Acta Math. Acad. Sci. Hungar.**11**(1960), 137–162. (unbound insert) (English, with Russian summary). MR**121870**, DOI 10.1007/BF02020631 - John Franco and Marvin Paull,
*Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem*, Discrete Appl. Math.**5**(1983), no. 1, 77–87. MR**678818**, DOI 10.1016/0166-218X(83)90017-3
frie E. Friedgut. Necessary and sufficient conditions for sharp thresholds of graph properties, and the $k$-SAT problem. - Alan Frieze and Stephen Suen,
*Analysis of two simple heuristics on a random instance of $k$-SAT*, J. Algorithms**20**(1996), no. 2, 312–355. MR**1379227**, DOI 10.1006/jagm.1996.0016
friezewormald A. Frieze and N. C. Wormald. Random $k$-SAT: a tight threshold for moderately growing $k$. In - Svante Janson, Yannis C. Stamatiou, and Malvina Vamvakari,
*Bounding the unsatisfiability threshold of random 3-SAT*, Random Structures Algorithms**17**(2000), no. 2, 103–116. MR**1774746**, DOI 10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.3.CO;2-G
342 A. Kaporis, L. M. Kirousis, and E. G. Lalas. The probabilistic analysis of a greedy satisfiability algorithm. In - Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C. Stamatiou,
*Approximating the unsatisfiability threshold of random formulas*, Random Structures Algorithms**12**(1998), no. 3, 253–269. MR**1635256**, DOI 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.3.CO;2-H
MPZ M. Mézard, G. Parisi, and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems. - Rémi Monasson and Riccardo Zecchina,
*Statistical mechanics of the random $K$-satisfiability model*, Phys. Rev. E (3)**56**(1997), no. 2, 1357–1370. MR**1464158**, DOI 10.1103/PhysRevE.56.1357
drunk I. Stewart. Where drunkards hang out.

*Proc. 43rd Annual Symposium on Foundations of Computer Science*, pages 126–127, 2002. BMZ A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Preprint, 2002.

*Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI-91) Vol. 1*, pages 331–337, 1991. mick V. Chvátal and B. Reed. Mick gets some (the odds are on his side). In

*Proc. 33rd Annual Symposium on Foundations of Computer Science*, pages 620–627, 1992.

*Proc. 11th Annual Symposium on Discrete Algorithms*, pages 126–127, 2000.

*J. Amer. Math. Soc.*, 12:1017–1054, 1999.

*Proc. 5th International Symposium on Theory and Applications of Satisfiability Testing*, pages 1–6, 2002.

*Proc. 10th Annual European Symposium on Algorithms*, volume 2461 of

*Lecture Notes in Computer Science*, pages 574–585. Springer, 2002.

*Science*, 297: 812-815, 2002. MZ M. Mézard and R. Zecchina. Random $K$-satisfiability: from an analytic solution to a new efficient algorithm.

*Phys. Rev. E*, 66, 056126, 2002. MSL D. G. Mitchell, B. Selman, and H. J. Levesque. Hard and easy distributions of SAT problems. In

*Proc. 10th National Conference on Artificial Intelligence*, pages 459–462, 1992.

*Nature*, News and Views, October 18, 2001.

## Additional Information

**Dimitris Achlioptas**- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
- Email: optas@microsoft.com
**Yuval Peres**- Affiliation: Department of Statistics, University of California, Berkeley, California 94720
- MR Author ID: 137920
- Email: peres@stat.berkeley.edu
- Received by editor(s): September 4, 2003
- Published electronically: August 27, 2004
- Additional Notes: This research was supported by NSF Grant DMS-0104073, NSF Grant DMS-0244479 and a Miller Professorship at UC Berkeley. Part of this work was done while visiting Microsoft Research.
- © Copyright 2004
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**17**(2004), 947-973 - MSC (2000): Primary 68R99, 82B26; Secondary 05C80
- DOI: https://doi.org/10.1090/S0894-0347-04-00464-3
- MathSciNet review: 2083472