In the last decades the tl1eory of spin glasses has been developed within the
framework of statistical physics. The obtained results showed to be novel
not only from the physical point of vie\l\'1 but they have brought also new
mathematical techniques and algorithmic approaches. Indeed, the problem
of finding ground state of a spin glass is (in general) NP-complete.
The methods that were found brought new ideas to the field of Combinatorial
Optimization, and on the other side, the similar methods of Combinatorial
Optimization, were applied in physical systems. As it happened with
the Monte Carlo sampling and the Simulated Annealing, also the novel Cavity
Method lead to algorithms that are open to wide use in various fields of
research The Cavity Method shows to be equivalent to Bethe Approximation
in its most symmetric version, and the derived algorithm is equivalent to the
Belief Propagation, an inference method used widely for example in the field
of Pattern Recognition.
The Cavity Method in a less symmetric situation, when one has to consider
correctly the clustering of the configuration space, lead to a novel messagepassing
algorithm-the Survey Propagation.
The class of Message-Passing algorithms, among which both the Belief
Propagation and the Survey Propagation belong, has found its application
as Inference Algorithms in many engineering fields. Among others let us
:mention the Low-Density Parity-Check Codes, that are widely used as ErrorCorrecting
Codes for communication over noisy cha1mels.
In the first part of this work we have compared efficiency of the Survey
Propagation Algorithm and of standard heuristic algorithms in the case of
the random-MAX-K-SAT problem. The results showed that the algorithms
perform similarly in the regions where the clustering of configuration space
does not appeai~ but that the Survey Propagation finds much better solutions
to the optimization problem in the critical region where one has to consider
existence of many ergodic components explicitly.
The second part of the thesis targets the problem of protein structure and
flexibility. In many proteins the mobility of certain regions and rigidity of
other regions of their structure is crucial for their function or interaction with
other cellular elements. Our simple model tries to point out the flexible regions
from the knowledge of native 3D-structure of the protein. The problem
is mapped to a spin glass model which is successfully solved by the Believe
Propagation algorithm.
