Unified survey-belief propagation approach for satisfiability

In this talk I shall discuss a modified message-passing BP (Belief Propagation) procedure, which can be generally used to minimize variational Bethe free energies in statistical physics. By a straightforward mapping, this algorithm can be easily applied to combinatorial optimization problems, such as 3-satisfiability, the prototype of NP-hard problems. I show that the method can be also extended to the framework of SP (Survey Propagation), a recently proposed algorithm which, still making use of techniques borrowed from statistical physics, overcomes problems encountered by local search algorithms on hard instances close to the ``SAT-UNSAT'' transition. This allows to obtain a unified and quite stable message passing scheme, which can be used both in the ``full replica-symmetry-breaking'' region, where ordinary Belief Propagation usually does not converge, and in the ``hard'' region near the sat-unsat transition, where it allows to solve subformulae generated by ``survey inspired decimation''.