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.
- naesat D. Achlioptas and C. Moore. The asymptotic order of the random $k$-SAT threshold. In 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.
- 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 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.
- 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 Proc. 11th Annual Symposium on Discrete Algorithms, pages 126–127, 2000.
- 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. J. Amer. Math. Soc., 12:1017–1054, 1999.
- 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 Proc. 5th International Symposium on Theory and Applications of Satisfiability Testing, pages 1–6, 2002.
- 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 Proc. 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 574–585. Springer, 2002.
- 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. 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.
- 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. Nature, News and Views, October 18, 2001.
- Dimitris Achlioptas
- Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
- Email: email@example.com
- Yuval Peres
- Affiliation: Department of Statistics, University of California, Berkeley, California 94720
- MR Author ID: 137920
- Email: firstname.lastname@example.org
- 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