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 条
[41]   Improving configuration checking for satisfiable random k-SAT instances [J].
Abrame, Andre ;
Habet, Djamal ;
Toumi, Donia .
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2017, 79 (1-3) :5-24
[42]   The asymptotic k-SAT threshold [J].
Coja-Oghlan, Amin ;
Panagiotou, Konstantinos .
ADVANCES IN MATHEMATICS, 2016, 288 :985-1068
[43]   The threshold for random k-SAT is 2k log 2-O(k) [J].
Achlioptas, D ;
Peres, Y .
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2004, 17 (04) :947-973
[44]   The Asymptotic k-SAT Threshold [J].
Coja-Oghlan, Amin .
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :804-813
[45]   FRACTAL STRUCTURE ON k-SAT [J].
Wang, Qin ;
Xi, Lifeng .
FRACTALS-COMPLEX GEOMETRY PATTERNS AND SCALING IN NATURE AND SOCIETY, 2011, 19 (02) :227-232
[46]   An Approximation Algorithm for #k-SAT [J].
Thurley, Marc .
29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 2012, 14 :78-87
[47]   Enumerating k-SAT functions [J].
Dong, Dingding ;
Mani, Nitya ;
Zhao, Yufei .
PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2022, :2141-2184
[48]   Approximating MIN k-SAT [J].
Avidor, A ;
Zwick, U .
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002, 2518 :465-475
[49]   Analysis of two simple heuristics on a random instance of k-SAT [J].
Frieze, A ;
Suen, S .
JOURNAL OF ALGORITHMS, 1996, 20 (02) :312-355
[50]   Threshold values of random K-SAT from the cavity method [J].
Mertens, S ;
Mézard, M ;
Zecchina, R .
RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (03) :340-373
12345