Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 

 

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


Authors: Dimitris Achlioptas and Yuval Peres
Journal: J. Amer. Math. Soc. 17 (2004), 947-973
MSC (2000): Primary 68R99, 82B26; Secondary 05C80
Published electronically: August 27, 2004
MathSciNet review: 2083472
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. A. Braunstein, M. Mézard, and R. Zecchina.
    Survey propagation: an algorithm for satisfiability.
    Preprint, 2002.
  • 3. Ming-Te Chao and John Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the 𝑘-satisfiability problem, Inform. Sci. 51 (1990), no. 3, 289–314. MR 1072035, 10.1016/0020-0255(90)90030-E
  • 4. 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.
  • 5. 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.
  • 6. N. G. de Bruijn, Asymptotic methods in analysis, 3rd ed., Dover Publications, Inc., New York, 1981. MR 671583
  • 7. 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, 10.1007/BF02401841
  • 8. 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
  • 9. O. Dubois and Y. Boufkhad, A general upper bound for the satisfiability threshold of random 𝑟-SAT formulae, J. Algorithms 24 (1997), no. 2, 395–420. MR 1469655, 10.1006/jagm.1997.0867
  • 10. 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.
  • 11. 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, North-Holland, Amsterdam, 1975, pp. 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. MR 0382050
  • 12. 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 0121870
  • 13. 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, 10.1016/0166-218X(83)90017-3
  • 14. 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.
  • 15. Alan Frieze and Stephen Suen, Analysis of two simple heuristics on a random instance of 𝑘-SAT, J. Algorithms 20 (1996), no. 2, 312–355. MR 1379227, 10.1006/jagm.1996.0016
  • 16. 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.
  • 17. 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, 10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.3.CO;2-G
  • 18. 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.
  • 19. 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, 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.3.CO;2-H
  • 20. M. Mézard, G. Parisi, and R. Zecchina.
    Analytic and Algorithmic Solution of Random Satisfiability Problems.
    Science, 297: 812-815, 2002.
  • 21. M. Mézard and R. Zecchina.
    Random $K$-satisfiability: from an analytic solution to a new efficient algorithm.
    Phys. Rev. E, 66, 056126, 2002.
  • 22. 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.
  • 23. Rémi Monasson and Riccardo Zecchina, Statistical mechanics of the random 𝐾-satisfiability model, Phys. Rev. E (3) 56 (1997), no. 2, 1357–1370. MR 1464158, 10.1103/PhysRevE.56.1357
  • 24. I. Stewart.
    Where drunkards hang out.
    Nature, News and Views, October 18, 2001.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 68R99, 82B26, 05C80

Retrieve articles in all journals with MSC (2000): 68R99, 82B26, 05C80


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
Email: peres@stat.berkeley.edu

DOI: http://dx.doi.org/10.1090/S0894-0347-04-00464-3
Keywords: Satisfiability, random formulas, phase transitions
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.
Article copyright: © Copyright 2004 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.