Random k-SAT: A tight threshold for moderately growing k
| Author(s) : | Nicholas C. Wormald, |
| Publisher : | N/A |
| Publication Date : | 2002 |
| ISSN : | N/A |
| Abstract : | We consider a random instance I of k-SAT with n variables and m clauses, where k = k(n) satisfies k ? log 2 n ? ?. Let m0 = 2 k n ln 2 and let = (n)> 0 be such that n ? ?. We prove that 1, |