Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\) (Q1010652): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q583109 |
||
| Property / author | |||
| Property / author: Q228771 / rank | |||
Revision as of 07:20, 16 February 2024
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
