A novel weighting scheme for random $k$-SAT

Abstract

Consider a random $k$-CNF formula $F_k(n,rn)$ with $n$ variables and $rn$ clauses. For every truth assignment $\ddot{I}ƒ\in \{0,1{\}}^n$ and every clause $c={\ell }_1\vee \cdots \vee {\ell }_k$, let $d=d(\ddot{I}ƒ,c)$ be the number of satisfied literal occurrences in $c$ under $\ddot{I}ƒ$. For fixed ${\hat{I}}^2>-1$ and $\hat{I}»>0$, we take $\ddot{I}‰(\ddot{I}ƒ,c)=0$, if $d=0$; $\ddot{I}‰(\ddot{I}ƒ,c)=\hat{I}»(1+{\hat{I}}^2)$, if $d=1$ and $\ddot{I}‰(\ddot{I}ƒ,c)=\hat{I}{»}^d$, if $d>1$. Applying the above weighting scheme, we get that if $F_k(n,rn)$ is unsatisfiable with probability tending to one as $n\to \infty$, then $r\ge 2.83,8.09,18.91,40.81,84.87$ for $k=3,4,5,6$ and $7,$ respectively.

8 pages. arXiv admin note: text overlap with arXiv:cs/0305009 by other authors