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] Strong refutation heuristics for random k-SAT [J].

Coja-Oghlan, Amin ;

Goerdt, Andreas ;

Lanka, Andre .

COMBINATORICS PROBABILITY & COMPUTING, 2007, 16 (01) :5-28

[22] Bounds on Threshold of Regular Random k-SAT [J].

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 [J].

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 [J].

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 [J].

Braunstein, A ;

Zecchina, R .

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, 2004, 2919 :519-528

[26] Random k-SAT and the power of two choices [J].

Perkins, Will .

RANDOM STRUCTURES & ALGORITHMS, 2015, 47 (01) :163-173

[27] A novel weighting scheme for random k-SAT关于随机 k-SAT 的新加权方法 [J].

Jun Liu ;

Ke Xu .

Science China Information Sciences, 2016, 59

[28] Complexity of k-SAT [J].

Impagliazzo, R ;

Paturi, R .

FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, :237-240

[29] Regular Random k-SAT: Properties of Balanced Formulas [J].

Yacine Boufkhad ;

Olivier Dubois ;

Yannet Interian ;

Bart Selman .

Journal of Automated Reasoning, 2005, 35 :181-200

[30] On the complexity of k-SAT [J].

Impagliazzo, R ;

Paturi, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2001, 62 (02) :367-375

← 1 2 3 4 5 →