Abstract

Let Z(F)Z(F) be the number of solutions of a random kk-satisfiability formula FF with nn variables and clause density αα. Assume that the probability that FF is unsatisfiable is $O(1/\log(n)^{1+\e})$ for $\e>0$. We show that (possibly excluding a countable set of `exceptional' αα's) the number of solutions concentrate in the logarithmic scale, i.e., there exists a non-random function ϕ(α)ϕ(α) such that, for any δ>0δ>0, (1/n)log⁡Z(F)∈[ϕ−δ,ϕ+δ](1/n)\log Z(F)\in [ϕ-δ,ϕ+δ] with high probability. In particular, the assumption holds for all α<1α<1, which proves the above concentration claim in the whole satisfiability regime of random 22-SAT. We also extend these results to a broad class of constraint satisfaction problems. The proof is based on an interpolation technique from spin-glass theory, and on an application of Friedgut's theorem on sharp thresholds for graph properties.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.