Analysing Survey Propagation Guided Decimation on Random Formulas

Abstract

Let $\Phi$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. For clauses/variables ratio $m/n\le r_{k\text{-SAT}}\sim 2^k\ln 2$ the formula $\Phi$ is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond $m/n\sim 2k\ln (k)/k$ with a non-vanishing probability. Non-rigorous statistical mechanics work on $k$-CNF led to the development of a new efficient "message passing algorithm" called \emph{Survey Propagation Guided Decimation} [Mézard et al., Science 2002]. Experiments conducted for $k=3,4,5$ suggest that the algorithm finds satisfying assignments close to $r_{k\text{-SAT}}$. However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random $k$-SAT formulas efficiently already for $m/n=2^k(1+{\epsilon }_k)\ln (k)/k$ with ${\lim }_{k\to \infty }{\epsilon }_k=0$ almost a factor $k$ below $r_{k\text{-SAT}}$.

arXiv admin note: substantial text overlap with arXiv:1007.1328 by other authors

Cited by in corpus (4)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems