pith. sign in

arxiv: 1310.4303 · v1 · pith:55PHQ2ZKnew · submitted 2013-10-16 · 💻 cs.DM

A novel weighting scheme for random k-SAT

classification 💻 cs.DM
keywords sigmalambdaomegabetaeveryrandomschemeweighting
0
0 comments X
read the original abstract

Consider a random $k$-CNF formula $F_{k}(n, rn)$ with $n$ variables and $rn$ clauses. For every truth assignment $\sigma\in \{0, 1\}^{n}$ and every clause $c=\ell_{1}\vee\cdots\vee\ell_{k}$, let $d=d(\sigma, c)$ be the number of satisfied literal occurrences in $c$ under $\sigma$. For fixed $\beta>-1$ and $\lambda>0$, we take $\omega(\sigma, c)=0$, if $d=0$; $\omega(\sigma, c)=\lambda(1+\beta)$, if $d=1$ and $\omega(\sigma, c)=\lambda^{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\rightarrow\infty$, then $r\geq2.83, 8.09, 18.91, 40.81, 84.87$ for $k=3, 4, 5, 6$ and $7,$ respectively.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.