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 条

[21] A novel weighting scheme for random k-SAT
Liu, Jun
Xu, Ke
SCIENCE CHINA-INFORMATION SCIENCES, 2016, 59 (09)
[22] Bounds on Threshold of Regular Random k-SAT
Rathi, Vishwambhar
Aurell, Erik
Rasmussen, Lars
Skoglund, Mikael
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2010, PROCEEDINGS, 2010, 6175 : 264 - 277
[23] Strong refutation heuristics for random k-SAT
Coja-Oghlan, A
Goerdt, A
Lanka, A
APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, PROCEEDINGS, 2004, 3122 : 310 - 321
[24] The asymptotic order of the random k-SAT threshold
Achlioptas, D
Moore, C
FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2002, : 779 - 788
[25] Survey and Belief Propagation on random K-SAT
Braunstein, A
Zecchina, R
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, 2004, 2919 : 519 - 528
[26] Random k-SAT and the power of two choices
Perkins, Will
RANDOM STRUCTURES & ALGORITHMS, 2015, 47 (01) : 163 - 173
[27] A novel weighting scheme for random k-SAT关于随机 k-SAT 的新加权方法
Jun Liu
Ke Xu
Science China Information Sciences, 2016, 59
[28] Complexity of k-SAT
Impagliazzo, R
Paturi, R
FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, : 237 - 240
[29] On the complexity of k-SAT
Impagliazzo, R
Paturi, R
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 62 (02) : 367 - 375
[30] Regular Random k-SAT: Properties of Balanced Formulas
Yacine Boufkhad
Olivier Dubois
Yannet Interian
Bart Selman
Journal of Automated Reasoning, 2005, 35 : 181 - 200

← 1 2 3 4 5 →