期刊:Combinatorics, Probability & Computing [Cambridge University Press] 日期:1995-09-01卷期号:4 (03): 189-195被引量:28
标识
DOI:10.1017/s0963548300001590
摘要
Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.