
The Library
Random k-SAT : the limiting probability for satisfiability for moderately growing k
Tools
Coja-Oghlan, Amin and Frieze, Alan (2008) Random k-SAT : the limiting probability for satisfiability for moderately growing k. Electronic Journal of Combinatorics, Vol.15 . N2. ISSN 1077-8926.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||
Publisher: | Electronic Journal of Combinatorics | ||||
ISSN: | 1077-8926 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.15 | ||||
Page Range: | N2 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |