logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 9: 092101(2016) https://doi.org/10.1007/s11432-016-5526-8

A novel weighting scheme for random $k$-SAT

More info
  • ReceivedSep 28, 2015
  • AcceptedNov 3, 2015
  • PublishedAug 23, 2016

Abstract

Consider a random $k$-conjunctive normal form $F_{k}(n, rn)$ with $n$ variables and $rn$ clauses. We prove that if the probability that the formula $F_{k}(n, rn)$ is satisfiable tends to 0 as $n\rightarrow\infty$, then $r\geq2.83$, 8.09, 18.91, 40.81, and 84.87, for $k=3$, 4, 5, 6, and 7, respectively.


Funded by

National Natural Science Foundation of China(11371225)

Fund of the State Key Lab of Software Development Environment(SKLSDE-2015ZX-05)


Acknowledgment

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant No. 11371225) and Fund of the State Key Lab of Software Development Environment (Grant No. SKLSDE-2015ZX-05).


References

[1] Achlioptas D, Peres Y. The threshold for random k-SAT is $2^{k}\log 2-O(k)$. J Amer Math Soc, 2004, 17: 947-973 CrossRef Google Scholar

[2] Frieze A, Wormald N C. Random k-SAT: a tight threshold for moderately growing $k$. Combinatorica, 2005, 25: 297-305 CrossRef Google Scholar

[3] Liu J, Gao Z S, Xu K. A Note on Random k-SAT for Moderately Growing k. Electron J Combin, 2012, 19: 24-305 Google Scholar

[4] Achlioptas D, Moore C. Ramdom $k$-SAT: two moments suffice to cross a sharp threshold. SIAM J Comput, 2006, 36: 740-762 CrossRef Google Scholar

[5] Achlioptas D, Moore C. The asymptotic order of the random k-SAT threshold. In: Proceeding of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, 2002. 126--127. Google Scholar

[6] Chvátal V, Reed B. Mick gets some (the odds are on his side). In: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 1992. 620--627. Google Scholar

[7] Erd\H{o}s P, Lovász L. Problems and results on 3-chromatic hypergraphs and some related questions. Colloq Math Soc J' a nos Bolyai, 1973, 10: 609-627 Google Scholar

[8] Friedgut E. Necessary and sufficient conditions for sharp thresholds of graph properties, and the $k$-SAT problem. J Amer Math Soc, 1999, 12: 1017-1054 CrossRef Google Scholar

[9] Janson S, Stamatiou Y C, Vamvakari M. Bounding the unsatisfiability threshold of random 3-SAT. Random Struct Algor, 2000, 17: 103-116 CrossRef Google Scholar

[10] Ding J, Sly A, Sun N. Proof of the satisfiability conjecture for large $k$. arXiv:1411.0650. Google Scholar

[11] Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Algor, 2006, 28: 444-480 CrossRef Google Scholar

[12] Vorobyev F Y. A lower bound for the 4-satisfiability threshold. Discrete Math Appl, 2007, 17: 287-294 Google Scholar

[13] de Bruijn N G. Asymptotic Methods in Analysis. 3rd ed. New York: Dover Publications Inc, 1981. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1