Geodesic
Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :