The asymptotic k-SAT threshold

被引：43
|
作者：
Coja-Oghlan, Amin [1 ]
Panagiotou, Konstantinos [2 ]
机构：
[1] Goethe Univ Frankfurt, Math Inst, 10 Robert Mayer St, D-60325 Frankfurt, Germany
[2] Univ Munich, Math Inst, D-80333 Munich, Germany
来源：
ADVANCES IN MATHEMATICS | 2016年 / 288卷
基金：
欧洲研究理事会;
关键词：
Phase transitions; Satisfiability problem; Probabilistic combinatorics; SATISFIABILITY; ALGORITHM; PROOF;
D O I：
10.1016/j.aim.2015.11.007
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Since the early 20005 physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures on phase transitions in random problems (Mezard et al., 2002 [37]). The cavity method predicts that the satisfiability threshold in the random k-SAT problem is r(k-SAT) = 2(k) in 2 - 1/2 (1 + ln2) + epsilon(k), with lim(k ->infinity) epsilon(k) = 0 (Mertens et al., 2006 [35]). This paper contains a proof of the conjecture. (C) 2015 Elsevier Inc. All rights reserved.
引用
收藏
页码：985 / 1068
页数：84
相关论文
共 50 条
  • [1] The Asymptotic k-SAT Threshold
    Coja-Oghlan, Amin
    STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 804 - 813
  • [2] 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
  • [3] Going After the k-SAT Threshold
    Coja-Oghlan, Amin
    Panagiotou, Konstantinos
    STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2013, : 705 - 714
  • [4] 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
  • [5] On threshold properties of k-SAT:: An additive viewpoint
    Plagne, Alain
    EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (07) : 1186 - 1198
  • [6] Satisfiability threshold of the skewed random k-SAT
    Sinopalnikov, DA
    THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, 2005, 3542 : 263 - 275
  • [7] Random k-SAT:: A tight threshold for moderately growing k
    Frieze, A
    Wormald, NC
    COMBINATORICA, 2005, 25 (03) : 297 - 305
  • [8] Random k-Sat: A Tight Threshold For Moderately Growing k
    Alan Frieze*
    Nicholas C. Wormald†
    Combinatorica, 2005, 25 : 297 - 305
  • [9] Complexity of k-SAT
    Impagliazzo, R
    Paturi, R
    FOURTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1999, : 237 - 240
  • [10] Threshold values of random K-SAT from the cavity method
    Mertens, S
    Mézard, M
    Zecchina, R
    RANDOM STRUCTURES & ALGORITHMS, 2006, 28 (03) : 340 - 373
12345