Analysing Survey Propagation Guided Decimation on Random Formulas

Let varPhi be a uniformly distributed random k-SAT formula with n variables and m clauses. For clauses/variables ratio m/n ≤ rk-SAT ~ 2kln2 the formula varPhi is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond m/n ~ 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 Survey Propagation Guided Decimation [M'ezard et al., Science 2002]. Experiments conducted for k=3,4,5 suggest that the algorithm finds satisfying assignments close to rk-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=2k(1+varepsilonk)ln(k)/k with limk→∞varepsilonk= 0 almost a factor k below rk-SAT.