Geodesic
Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
We consider a random instance $I_m=I_{m,n,k}$ of $k$-SAT with $n$ variables and $m$ clauses, where $k=k(n)$ satisfies $k-\log_2 n\to\infty$. Let $m=2^k(n\ln 2+c)$ for an absolute constant $c$. We prove that $$\lim_{n\to\infty}\Pr(I_m\hbox{ is satisfiable})=e^{-e^{-c}}.$$
DOI : 10.37236/877
Classification : 68T20, 60C05, 68Q25 
Amin Coja-Oghlan; Alan Frieze. Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\). The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/877
@article{10_37236_877,
     author = {Amin Coja-Oghlan and Alan Frieze},
     title = {Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/877},
     zbl = {1163.68337},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/877/}
}
TY  - JOUR
AU  - Amin Coja-Oghlan
AU  - Alan Frieze
TI  - Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/877/
DO  - 10.37236/877
ID  - 10_37236_877
ER  - 
%0 Journal Article
%A Amin Coja-Oghlan
%A Alan Frieze
%T Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/877/
%R 10.37236/877
%F 10_37236_877

Cité par Sources :