Geodesic
A note on random \(k\)-SAT for moderately growing \(k\)
The electronic journal of combinatorics, Tome 19 (2012) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Consider a random instance $I$ of $k$-SAT with $n$ variables and $m$ clauses. Suppose that $\theta$, $c>0$ are any fixed real numbers. Let $k=k(n)\geq \big(\frac{1}{2}+\theta\big)\log_{2}n$. We prove that \begin{align}\nonumber\lim_{n\rightarrow\infty}Pr(I\ \mbox{is satifiable})=\left\{\begin{array}{cc}1&m\leq\big(1-\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2 \\0&m\geq\big(1+\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2. \\\end{array}\right.\end{align}
DOI : 10.37236/1176
Classification : 68Q87, 05D40, 68Q25
Mots-clés : k-SAT, phase transition, second moment method 
@article{10_37236_1176,
     author = {Jun Liu and Zongsheng Gao and Ke Xu},
     title = {A note on random {\(k\)-SAT} for moderately growing \(k\)},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {1},
     doi = {10.37236/1176},
     zbl = {1288.68185},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1176/}
}
TY  - JOUR
AU  - Jun Liu
AU  - Zongsheng Gao
AU  - Ke Xu
TI  - A note on random \(k\)-SAT for moderately growing \(k\)
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1176/
DO  - 10.37236/1176
ID  - 10_37236_1176
ER  - 
%0 Journal Article
%A Jun Liu
%A Zongsheng Gao
%A Ke Xu
%T A note on random \(k\)-SAT for moderately growing \(k\)
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1176/
%R 10.37236/1176
%F 10_37236_1176
Jun Liu; Zongsheng Gao; Ke Xu. A note on random \(k\)-SAT for moderately growing \(k\). The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/1176

Cité par Sources :