Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios

Abstract

For large clause-to-variable ratio, typical K-SAT instances drawn from the uniform distribution have no solution. We argue, based on statistical mechanics calculations using the replica and cavity methods, that rare satisfiable instances from the uniform distribution are very similar to typical instances drawn from the so-called planted distribution, where instances are chosen uniformly between the ones that admit a given solution. It then follows, from a recent article by Feige, Mossel and Vilenchik, that these rare instances can be easily recognized (in O(log N) time and with probability close to 1) by a simple message-passing algorithm.

8 pages of text and 7 of appendices; updated to take into account comments received on the first version; to be published on J.Phys.A:Math.Gen

Cited by in corpus (9)

• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Large Deviations in the Free-Energy of Mean-Field Spin-Glasses
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Phase diagram and large deviations in the free-energy of mean-field spin-glasses
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT
• Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates