Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
Summary: We consider a random instance \(I_m=I_{m,n,k}\) of \(k\)-SAT with \(n\) variables and \(m\) clauses, where \(k=k(n)\) satisfies \(k-\log_2 n\to\infty\). Let \(m=2^k(n\ln 2+c)\) for an absolute constant \(c\). We prove that \[ \lim_{n\to\infty}\text{Pr}(I_m\text{ is satisfiable})=e^{-e^{-c}}. \]
scientific article; zbMATH DE number 5540864