Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) (Q1010652)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) |
scientific article; zbMATH DE number 5540864
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) |
scientific article; zbMATH DE number 5540864 |
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
0.95748514
0 references
0.9545043
0 references
0.9218999
0 references
0.91510105
0 references
0 references
0.9073564
0 references
0.9071507
0 references
0.90260124
0 references
