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 条
  • [1] A Note on Random k-SAT for Moderately Growing k
    Liu, Jun
    Gao, Zongsheng
    Xu, Ke
    ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (01):
  • [2] Random k-SAT:: A tight threshold for moderately growing k
    Frieze, A
    Wormald, NC
    COMBINATORICA, 2005, 25 (03) : 297 - 305
  • [3] Random k-Sat: A Tight Threshold For Moderately Growing k
    Alan Frieze*
    Nicholas C. Wormald†
    Combinatorica, 2005, 25 : 297 - 305
  • [4] Satisfiability threshold of the skewed random k-SAT
    Sinopalnikov, DA
    THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, 2005, 3542 : 263 - 275
  • [5] Satisfiability and Algorithms for Non-uniform Random k-SAT
    Omelchenko, Oleksii
    Bulatov, Andrei A.
    THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2021, 35 : 3886 - 3894
  • [6] Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT
    Friedrich, Tobias
    Rothenberger, Ralf
    PROCEEDINGS OF THE TWENTY-EIGHTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2019, : 6151 - 6155
  • [7] Polarised random k-SAT
    Danielsson, Joel Larsson
    Markstrom, Klas
    COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (06) : 885 - 899
  • [8] Biased random k-SAT
    Larsson, Joel
    Markstrom, Klas
    RANDOM STRUCTURES & ALGORITHMS, 2021, 59 (02) : 238 - 266
  • [9] On an online random k-SAT model
    Kravitz, David
    RANDOM STRUCTURES & ALGORITHMS, 2008, 32 (01) : 115 - 124
  • [10] On the behaviour of random K-SAT on trees
    Krishnamurthy, Supriya
    Sumedha
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2012,
12345