loading...
The Asymptotic Order of the Random k -SAT Threshold
Vancouver, BC, Canada November 16-November 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1182003The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Dimitris Achlioptas, Microsoft Research
Cristopher Moore, University of New Mexico and Santa Fe Institute
Form a random k-SAT formula on n variables by selecting uniformly and independently m = rn clauses out of all 2^k (_k^n ) possible k-clauses. The Satisfiability Threshold Conjecture asserts that for each k there exists a constant rk such that as n tends to infinity, the probability that the formula is satisfiable tends to 1 if r < rk and to 0 if r > rk. It has long been known that 2 k/k < rk > 2k. We prove that rk > 2k - 1 ln 2 - dk, where dk → (1 + ln 2)/2. Our proof also allows a blurry glimpse of the "geometry" of the set of satisfying truth assignments.
Citation:
Dimitris Achlioptas, Cristopher Moore, "The Asymptotic Order of the Random k -SAT Threshold," focs, pp.779, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.