Name
Abstract | ||
|---|---|---|
We consider a random instance I of k-SAT with n variables and m clauses, where k=k(n) satisfies k—log2 n→∞. Let m 0=2 k nln2 and let ∈=∈(n)0 be such that ∈n→∞. We prove that $${}^{{\lim }}_{{n \to \infty }} \Pr {\left( {I\;{\text{is}}\;{\text{satisfiable}}} \right)} = \left\{ {^{{1\;m \leqslant {\left( {1 - \in } \right)}m_{0} }}_{{0\;m \geqslant {\left( {1 + \in } \right)}m_{0} }} .} \right.$$ |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s00493-005-0017-3 | Combinatorica |
Keywords | Field | DocType |
satisfiability | Discrete mathematics,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
25 | 3 | 0209-9683 |
Citations | PageRank | References |
20 | 1.29 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan M. Frieze | 1 | 4837 | 787.00 |
| Nicholas C. Wormald | 2 | 1506 | 230.43 |