Premium
On the concentration of the number of solutions of random satisfiability formulas
Author(s) -
Abbe Emmanuel,
Montanari Andrea
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20501
Subject(s) - satisfiability , mathematics , countable set , constraint satisfaction problem , combinatorics , discrete mathematics , struct , class (philosophy) , random variable , constraint (computer aided design) , function (biology) , random function , statistics , computer science , geometry , artificial intelligence , evolutionary biology , probabilistic logic , biology , programming language
Let Z ( F ) be the number of solutions of a random k ‐satisfiability formula F with n variables and clause density α . Assume that the probability that F is unsatisfiable is O ( 1 / log ( n ) 1 + δ ) for some δ > 0 . We show that (possibly excluding a countable set of “exceptional” α 's) the number of solutions concentrates, i.e., there exists a non‐random function α ↦ ϕ s ( α ) such that, for any ε > 0 , we have Z ( F ) ∈ [ 2 n ( ϕ s − ε ) , 2 n ( ϕ s + ε ) ] with high probability. In particular, the assumption holds for all α < 1 , which proves the above concentration claim in the whole satisfiability regime of random 2‐SAT. We also extend these results to a broad class of constraint satisfaction problems. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 362–382, 2014