  Typical-case computation complexity is a research topic at the boundary of
computer science, applied mathematics, and statistical physics. In the last
twenty years the replica-symmetry-breaking mean field theory of spin glasses
and the associated message-passing algorithms have greatly deepened our
understanding of typical-case computation complexity. In this paper we use the
vertex cover problem, a basic nondeterministic-polynomial (NP)-complete
combinatorial optimization problem of wide application, as an example to
introduce the statistical physical methods and algorithms. We do not go into
the technical details but emphasize mainly the intuitive physical meanings of
the message-passing equations. A nonfamiliar reader shall be able to understand
to a large extent the physics behind the mean field approaches and to adjust
them in solving other optimization problems.
