On Random 3-sat
- 12 September 1995
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 4 (3) , 189-195
- https://doi.org/10.1017/s0963548300001590
Abstract
LetSbe a set ofmclauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} ofnpropositional variables and their negations. Letbe the set of all suchSwithm = cnfor a fixedc> 0. We show, improving significantly over the first moment upper bound, that ifmandntend to infinity with, then almost allare unsatisfiable.Keywords
This publication has 4 references indexed in Scilit:
- Tail bounds for occupancy and the satisfiability threshold conjecturePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Mick gets some (the odds are on his side) (satisfiability)Published by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability ProblemSIAM Journal on Computing, 1986
- Central and local limit theorems applied to asymptotic enumerationJournal of Combinatorial Theory, Series A, 1973