go-v.orgdoi

Random $k$-SAT: The Limiting Probability for Satisfiability for Moderately Growing $k$

Amin Coja‐Oghlan, ALAN M. FRIEZE · The Electronic Journal of Combinatorics · 2008

  • DOI 10.37236/877
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 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)