Random k-SAT:: the limiting probability for satisfiability for moderately growing k

被引：0
作者：
Coja-Oghlan, Amin [1 ]
Frieze, Alan [1 ]
机构：
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
来源：
ELECTRONIC JOURNAL OF COMBINATORICS | 2008年 / 15卷 / 01期
关键词：
D O I：
暂无
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We consider a random instance I-m = I-m,I-n,I-k of k-SAT with n variables and m clauses, where k = k(n) satisfies k - log(2) n -> infinity. Let m = 2(k) (n ln 2 + c) for an absolute constant c. We prove that (n ->infinity)lim Pr(I-m is satisfiable) =e(-e-c).
引用
收藏
页数：6
相关论文
共 50 条
[31]   An Efficient Approach to Solving Random k-sat Problems [J].
Gilles Dequen ;
Olivier Dubois .
Journal of Automated Reasoning, 2006, 37 :261-276
[32]   An efficient approach to solving random k-SAT problems [J].
Dequen, Gilles ;
Dubois, Olivier .
JOURNAL OF AUTOMATED REASONING, 2006, 37 (04) :261-276
[33]   On belief propagation guided decimation for random k-SAT [J].
Coja-Oghlan, Amin .
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, :957-966
[34]   kcnfs:: An efficient solver for random k-SAT formulae [J].
Dequen, G ;
Dubois, O .
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, 2004, 2919 :486-501
[35]   On Belief Propagation Guided Decimation for Random k-SAT [J].
Coja-Oghlan, Amin .
PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2011, :957-966
[36]   The high temperature case for the random K-sat problem [J].
Michel Talagrand .
Probability Theory and Related Fields, 2001, 119 :187-212
[37]   An efficient approach to solving random k-sat problems [J].
Dequen, Gilles ;
Dubois, Olivier .
Journal of Automated Reasoning, 2006, 37 (04) :261-276
[38]   The high temperature case for the random K-sat problem [J].
Talagrand, M .
PROBABILITY THEORY AND RELATED FIELDS, 2001, 119 (02) :187-212
[39]   Regular random k-SAT:: Properties of balanced formulas [J].
Boufkhad, Yacine ;
Dubois, Olivier ;
Interian, Yannet ;
Selman, Bart .
JOURNAL OF AUTOMATED REASONING, 2005, 35 (1-3) :181-200
[40]   The number of k-SAT functions [J].
Bollobás, B ;
Brightwell, GR .
RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (03) :227-247
12345