Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
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?)


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
PII: S 0894-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.