RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2007 Volume 19, Issue 2, Pages 101–108 (Mi dm25)

This article is cited 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$.

UDC: 519.7

Received: 15.06.2005

DOI: 10.4213/dm25


 English version:
Discrete Mathematics and Applications, 2007, 17:3, 287–294

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024