Remote Access Journal of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0894-0347-04-00464-3
Published electronically: August 27, 2004
MathSciNet review: 2083472
Full-text PDF

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, https://doi.org/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.
    Dover Publications Inc., New York, 3rd edition, 1981. MR 0671583 (83m:41028)
  • 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, https://doi.org/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, https://doi.org/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, https://doi.org/10.1007/BF02020631
  • 13. J. Franco and M. Paull.
    Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem.
    Discrete Appl. Math., 5(1):77-87, 1983. MR 0678818 (84e:68038)
  • 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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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: https://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.

American Mathematical Society