A novel weighting scheme for random k-SAT

2016 
Consider a random $k$-conjunctive normal form $F_{k}(n, rn)$ with $n$ variables and $rn$ clauses. We prove that if the probability that the formula $F_{k}(n, rn)$ is satisfiable tends to 0 as $n\rightarrow\infty$, then $r\geq2.83$, 8.09, 18.91, 40.81, and 84.87, for $k=3$, 4, 5, 6, and 7, respectively.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    17
    References
    5
    Citations
    NaN
    KQI
    []