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

来源：

关键词：

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 条

[21]

2-U

Mézard, M ;

Zecchina, R .

PHYSICAL REVIEW E, 2002, 66 (05) :27-056126

Mézard, M ;

Parisi, G ;

Zecchina, R .

[24]

MITCHELL D, 1992, AAAI-92 PROCEEDINGS : TENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, P459

[25] Statistical mechanics of the random K-satisfiability model [J].

Monasson, R ;

Zecchina, R .

[26]

STEWART I, 2001, NATURE NEWS VIE 1018