|
Statistical physics, optimization and coding theory
Riccardo Zecchina
Polytecnico di Torino (Italy) & Theory Group (Microsoft) The combinatorial problem of satisfying a given
set of constraints that depend on N discrete variables is a fundamental one in
optimization and coding theory. Even for
randomly generated problem instances, the question "does it exist a
variable assignment that satisfies all constraints?" may become extraordinarily difficult to solve
in some range of parameters where a glass phase sets in. We shall provide a brief review on the recent
advances in the statistical mechanics approach to these satisfiability problems
and show how the analytic results have helped to design a new class of
message-passing algorithms -- the Survey Propagation (SP) algorithms -- that
are able to solve efficiently some combinatorial problems known to be
difficult. |