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
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. M.-T. Chao and J. Franco.
    Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the $k$-satisfiability problem.
    Inform. Sci., 51(3):289-314, 1990. MR 1072035 (91g:68076)
  • 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. A. Dembo, Y. Peres, J. Rosen and O. Zeitouni.
    Thick points for planar Brownian motion and the Erdos-Taylor conjecture on random walk.
    Acta Math., 186:239-270, 2001. MR 1846031 (2002k:60106)
  • 8. A. Dembo and O. Zeitouni.
    Large deviations techniques and applications.
    Springer Verlag, New York, 2nd edition, 1998. MR 1619036 (99d:60030)
  • 9. O. Dubois and Y. Boufkhad.
    A general upper bound for the satisfiability threshold of random $r$-SAT formulae.
    J. Algorithms, 24(2):395-420, 1997. MR 1469655 (98e:68103)
  • 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. Erdos and L. Lovász.
    Problems and results on $3$-chromatic hypergraphs and some related questions.
    Colloq. Math. Soc. János Bolyai, Vol. 10, 609-627. MR 0382050 (52:2938)
  • 12. P. Erdos and S. J. Taylor.
    Some problems concerning the structure of random walk paths.
    Acta Sci. Hung. 11:137-162, 1960. MR 0121870 (22:12599)
  • 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. A. M. Frieze and S. Suen.
    Analysis of two simple heuristics on a random instance of $k$-SAT.
    J. Algorithms, 20(2):312-355, 1996. MR 1379227 (97c:68062)
  • 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. S. Janson, Y. C. Stamatiou, and M. Vamvakari.
    Bounding the unsatisfiability threshold of random 3-SAT.
    Random Structures Algorithms, 17(2):103-116, 2000. MR 1774746 (2001c:68065)
  • 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. L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. Stamatiou.
    Approximating the unsatisfiability threshold of random formulas.
    Random Structures Algorithms, 12(3):253-269, 1998. MR 1635256 (2000c:68069)
  • 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. Monasson and R. Zecchina.
    Statistical mechanics of the random ${K}$-satisfiability model.
    Phys. Rev. E (3), 56(2):1357-1370, 1997. MR 1464158 (98g:82022)
  • 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

Yuval Peres
Affiliation: Department of Statistics, University of California, Berkeley, California 94720

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