|
This article is cited in 4 scientific papers (total in 4 papers)
A lower bound for the 4-satisfiability threshold
F. Yu. Vorob'ev
Abstract:
Let $F_k(n,m)$ be a random $k$-conjunctive normal form obtained by selecting uniformly and independently $m$ out of all possible $k$-clauses on $n$ variables. We prove that if $F_4(n,rn)$ is unsatisfiable with probability tending to one as $n\to\infty$, then $r\ge8.09$. This sharpens the known lower bound $r\ge7.91$.
Received: 15.06.2005
Citation:
F. Yu. Vorob'ev, “A lower bound for the 4-satisfiability threshold”, Diskr. Mat., 19:2 (2007), 101–108; Discrete Math. Appl., 17:3 (2007), 287–294
Linking options:
https://www.mathnet.ru/eng/dm25https://doi.org/10.4213/dm25 https://www.mathnet.ru/eng/dm/v19/i2/p101
|
Statistics & downloads: |
Abstract page: | 405 | Full-text PDF : | 188 | References: | 37 | First page: | 4 |
|