Random \(k\)-SAT: A tight threshold for moderately growing \(k\) (Q2387184): Difference between revisions

In this paper a random instance \(I\) of \(k\)-SAT with \(n\) variables and \(m\) clauses, where \(k=k(n)\) satisfies \(k-\log_{2}n\rightarrow \infty \) is considered. Let \(m_{0}=-n\ln 2/\ln (1-2^{-k})=(2^{k}+O(1))n\ln 2\), so that \(2^{n}(1-2^{-k})^{m_{0}}=1\) and let \(\epsilon =\epsilon (n)>0\) be such that \(\epsilon n\rightarrow \infty \). Let \(I\) be a random instance of \(k\)-SAT with \(n\) variables and \(m\) clauses. By using the second moment method it is shown that \(\lim _{n\rightarrow \infty }\text{\textbf{Pr}(}I\) is satisfiable)