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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
5
Citations
NaN
KQI