Random $k$-SAT: The Limiting Probability for Satisfiability for Moderately Growing $k$
Amin Coja‐Oghlan, ALAN M. FRIEZE · The Electronic Journal of Combinatorics · 2008
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2008
Abstract
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}}.$$
Open the resolved locator · 10.37236/877
Metadata licence: OpenAlex metadata (CC0)