arXiv (Cornell University) · 2016 · 12 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsProbability TheoryTheory Of ComputationApproximation AlgorithmsComputational ComplexityRandomized ComputationComplexity Of SatisfiabilityMessage-passing Algorithms
Let $\varPhi$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. For clauses/variables ratio $m/n \leq r_{k\text{-SAT}} \sim 2^k\ln2$ the formula $\varPhi$ 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+\varepsilon_k)\ln(k)/k$ with $\lim_{k\to\infty}\varepsilon_k= 0$ almost a factor $k$ below $r_{k\text{-SAT}}$.
7
Where the really hard problems are
Peter Cheeseman, Bob Kanefsky, William M. Taylor · 1991 · 1K citations
Analysis of Two Simple Heuristics on a Random Instance ofk-sat
Alan Frieze, Stephen Suen · Journal of Algorithms · 1996 · 227 citations
Limits of local algorithms over sparse random graphs
David Gamarnik, Madhu Sudan · 2014 · 107 citations
Optimal myopic algorithms for random 3-SAT
D. Achioptas, Gregory B. Sorkin · 2002 · 93 citations