Counting good truth assignments of random k-SAT formulae

2006/07/14 by Andrea Montanari, Devavrat Shah, Montanari, Andrea +1 · 1 citation
Computer Science · Physics and Astronomy · #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #Logic, Reasoning, and Knowledge #cond-mat.dis-nn #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0607073

13 pages, 1 eps figure

arxiv created 2006/07/14 · arxiv updated 2009/12/01

Abstract

We present a deterministic approximation algorithm to compute logarithm of the number of `good' truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (by `good' we mean that violate a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant epsilon with high probability as long as the clause density (ratio of clauses to variables) alpha<alpha_u(k) = 2k^-1log k(1+o(1)). The algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. This scheme substitutes the traditional one based on approximation of marginal probabilities via MCMC, in conjunction with self-reduction, which is not easy to extend to the present problem. We derive 2k^-1log k (1+o(1)) as threshold for uniqueness of the Gibbs distribution on satisfying assignment of random infinite tree k-SAT formulae to establish our results, which is of interest in its own right.

Cited by

• Random sampling of colourings of sparse random graphs with a constant number of colours

Related

• The Asymptotic Order of the k-SAT Threshold
• SARRIGUREN: a polynomial-time complete algorithm for random k-SAT with relatively dense clauses
• The number of satisfying assignments of random regular k-SAT formulas
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• The Threshold for Random k-SAT is 2^k ln2 - O(k)