Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
type: Item
instance of: scholarly article
title: Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)
zbMATH Open document ID: 1163.68337
author: Amin Coja-Oghlan
author: Alan Frieze
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/130036
full work available at URL: v15i1n2.html
review text: Summary: 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}\text{Pr}(I_m\text{ is satisfiable})=e^{-e^{-c}}. \]
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5540864
MaRDI profile type: Publication
Recommended article: Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
Recommended article: A note on random \(k\)-SAT for moderately growing \(k\)
Recommended article: On the critical exponents of random k‐SAT
Recommended article: Bounds on Threshold of Regular Random k-SAT
Recommended article: Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT
Recommended article: The Number of Satisfying Assignments of Random Regulark-SAT Formulas
Recommended article: Theory and Applications of Satisfiability Testing
Recommended article: A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
Recommended article: On the concentration of the number of solutions of random satisfiability formulas
description: scientific article; zbMATH DE number 5540864