zbMATH — the first resource for mathematics

The threshold for random \(k\)-SAT is \(2^k\log 2-O(k)\). (English) Zbl 1093.68075
Summary: Let \(F_k(n,m)\) be a random \(k\)-CNF formula formed by selecting uniformly and independently \(m\) out of all possible \(k\)-clauses on \(n\) variables. It is well known that if \(r \geq 2^k \log 2\), then \(F_k(n,rn)\) is unsatisfiable with probability that tends to 1 as \(n \to \infty\). We prove that if \(r \leq 2^k \log 2- t_k\), where \(t_k = O(k)\), then \(F_k(n,rn)\) is satisfiable with probability that tends to 1 as \(n \to \infty\).
Our technique, in fact, yields an explicit lower bound for the random \(k\)-SAT threshold for every \(k\). For \(k \geq 4\) our bounds improve all previously known such bounds.

68R99 Discrete mathematics in relation to computer science
05C80 Random graphs (graph-theoretic aspects)
06E30 Boolean functions
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI arXiv
[1] D. Achlioptas and C. Moore. The asymptotic order of the random \(k\)-SAT threshold. In Proc. 43rd Annual Symposium on Foundations of Computer Science, pages 126-127, 2002.
[2] A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: an algorithm for satisfiability. Preprint, 2002. · Zbl 1087.68126
[3] Ming-Te Chao and John Franco, Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the \?-satisfiability problem, Inform. Sci. 51 (1990), no. 3, 289 – 314. · Zbl 0706.68053 · doi:10.1016/0020-0255(90)90030-E · doi.org
[4] P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proc. 12th International Joint Conference on Artificial Intelligence (IJCAI-91) Vol. 1, pages 331-337, 1991. · Zbl 0747.68064
[5] V. Chvátal and B. Reed. Mick gets some (the odds are on his side). In Proc. 33rd Annual Symposium on Foundations of Computer Science, pages 620-627, 1992. · Zbl 0977.68538
[6] N. G. de Bruijn, Asymptotic methods in analysis, 3rd ed., Dover Publications, Inc., New York, 1981. · Zbl 0556.41021
[7] Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni, Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk, Acta Math. 186 (2001), no. 2, 239 – 270. · Zbl 1008.60063 · doi:10.1007/BF02401841 · doi.org
[8] Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications, 2nd ed., Applications of Mathematics (New York), vol. 38, Springer-Verlag, New York, 1998. · Zbl 0896.60013
[9] O. Dubois and Y. Boufkhad, A general upper bound for the satisfiability threshold of random \?-SAT formulae, J. Algorithms 24 (1997), no. 2, 395 – 420. · Zbl 0883.68065 · doi:10.1006/jagm.1997.0867 · doi.org
[10] O. Dubois, Y. Boufkhad, and J. Mandler. Typical random 3-SAT formulae and the satisfiability threshold. In Proc. 11th Annual Symposium on Discrete Algorithms, pages 126-127, 2000. · Zbl 0959.68135
[11] P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 609 – 627. Colloq. Math. Soc. János Bolyai, Vol. 10.
[12] P. Erdős and S. J. Taylor, Some problems concerning the structure of random walk paths, Acta Math. Acad. Sci. Hungar. 11 (1960), 137 – 162. (unbound insert) (English, with Russian summary). · Zbl 0091.13303 · doi:10.1007/BF02020631 · doi.org
[13] John Franco and Marvin Paull, Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem, Discrete Appl. Math. 5 (1983), no. 1, 77 – 87. · Zbl 0497.68021 · doi:10.1016/0166-218X(83)90017-3 · doi.org
[14] E. Friedgut. Necessary and sufficient conditions for sharp thresholds of graph properties, and the \(k\)-SAT problem. J. Amer. Math. Soc., 12:1017-1054, 1999. · Zbl 0932.05084
[15] Alan Frieze and Stephen Suen, Analysis of two simple heuristics on a random instance of \?-SAT, J. Algorithms 20 (1996), no. 2, 312 – 355. · Zbl 0852.68038 · doi:10.1006/jagm.1996.0016 · doi.org
[16] A. Frieze and N. C. Wormald. Random \(k\)-SAT: a tight threshold for moderately growing \(k\). In Proc. 5th International Symposium on Theory and Applications of Satisfiability Testing, pages 1-6, 2002. · Zbl 1083.68048
[17] Svante Janson, Yannis C. Stamatiou, and Malvina Vamvakari, Bounding the unsatisfiability threshold of random 3-SAT, Random Structures Algorithms 17 (2000), no. 2, 103 – 116. , https://doi.org/10.1002/1098-2418(200009)17:23.3.CO;2-G · Zbl 0958.03028
[18] A. Kaporis, L. M. Kirousis, and E. G. Lalas. The probabilistic analysis of a greedy satisfiability algorithm. In Proc. 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 574-585. Springer, 2002. · Zbl 1019.68814
[19] Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Yannis C. Stamatiou, Approximating the unsatisfiability threshold of random formulas, Random Structures Algorithms 12 (1998), no. 3, 253 – 269. , https://doi.org/10.1002/(SICI)1098-2418(199805)12:33.3.CO;2-H · Zbl 0936.68038
[20] M. Mézard, G. Parisi, and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297: 812-815, 2002.
[21] M. Mézard and R. Zecchina. Random \(K\)-satisfiability: from an analytic solution to a new efficient algorithm. Phys. Rev. E, 66, 056126, 2002.
[22] D. G. Mitchell, B. Selman, and H. J. Levesque. Hard and easy distributions of SAT problems. In Proc. 10th National Conference on Artificial Intelligence, pages 459-462, 1992.
[23] Rémi Monasson and Riccardo Zecchina, Statistical mechanics of the random \?-satisfiability model, Phys. Rev. E (3) 56 (1997), no. 2, 1357 – 1370. · doi:10.1103/PhysRevE.56.1357 · doi.org
[24] I. Stewart. Where drunkards hang out. Nature, News and Views, October 18, 2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.