On the concentration of the number of solutions of random satisfiability formulas |
| |
Authors: | Emmanuel Abbe Andrea Montanari |
| |
Affiliation: | 1. Department of Electrical Engineering and Program in Applied and Computational Mathematics, Princeton University;2. Department of Electrical Engineering and Department of Statistics, Stanford University |
| |
Abstract: | 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 for some . We show that (possibly excluding a countable set of “exceptional” α's) the number of solutions concentrates, i.e., there exists a non‐random function such that, for any , we have with high probability. In particular, the assumption holds for all , 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 |
| |
Keywords: | constraint satisfaction problems satisfiability counting concentration sharp threshold interpolation method |
|
|