  An overview of some methods of statistical physics applied to the analysis of
algorithms for optimization problems (satisfiability of Boolean constraints,
vertex cover of graphs, decoding, ...) with distributions of random inputs is
proposed. Two types of algorithms are analyzed: complete procedures with
backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local
search procedures (gradient descent, random walksat, ...). The study of
complete algorithms makes use of physical concepts such as phase transitions,
dynamical renormalization flow, growth processes, ... As for local search
procedures, the connection between computational complexity and the structure
of the cost function landscape is questioned, with emphasis on the notion of
metastability.
