The threshold for random k-SAT is 2k log 2-O(k)

被引：131
作者：
Achlioptas, D
Peres, Y
机构：
[1] Microsoft Corp, Res, Redmond, WA 98052 USA
[2] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA
来源：
JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY | 2004年 / 17卷 / 04期
关键词：
satisfiability; random formulas; phase transitions;
D O I：
10.1090/S0894-0347-04-00464-3
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
[No abstract available]
引用
收藏
页码：947 / 973
页数：27
相关论文
共 26 条
[1]  
ACHLIOPTAS D, 2002, P 43 ANN S FDN COMP, P126
[2]  
[Anonymous], C MATH SOC J BOLYAI
[3]  
Braunstein A., 2002, Survey propagation: an algorithm for satisfiability
[4]  
CHAO MT, 1990, INFORM SCIENCES, V51, P289, DOI 10.1016/0020-0255(90)90030-E
[5]  
Cheeseman P., 1991, PROC 12 IJCAI, P331, DOI [DOI 10.5555/1631171.1631221, 10.5555/1631171.1631221]
[6]  
CHVATAL V, 1992, AN S FDN CO, P620
[7]  
De Bruijn NG., 1981, Asymptotic Methods in Analysis, V4
[8]   Thick points for planar Brownian motion and the Erdos-Taylor conjecture on random walk [J].
Dembo, A ;
Peres, Y ;
Rosen, J ;
Zeitouni, O .
ACTA MATHEMATICA, 2001, 186 (02) :239-270
[9]  
Dembo A., 2010, Large Deviations Techniques and Applications
[10]   A general upper bound for the satisfiability threshold of random r-SAT formulae [J].
Dubois, O ;
Boufkhad, Y .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1997, 24 (02) :395-420
123