Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) (Q1010652)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) |
scientific article |
Statements
Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) (English)
0 references
7 April 2009
0 references
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}}. \]
0 references
