Affordable Access

Random k-SAT : the limiting probability for satisfiability for moderately growing k

Authors
Publisher
Electronic Journal of Combinatorics
Publication Date
Keywords
  • Qa Mathematics

Abstract

We consider a random instance Im=Im,n,k of k-SAT with n variables and m clauses, where k=k(n) satisfies k−log2n→∞. Let m=2k(nln2+c) for an absolute constant c. We prove that limn→∞Pr(Im is satisfiable)=e−e−c.

There are no comments yet on this publication. Be the first to share your thoughts.