The cavity method is a mathematical method presented by
Marc Mézard,
Giorgio Parisi
Giorgio Parisi (born 4 August 1948) is an Italian theoretical physicist, whose research has focused on quantum field theory, statistical mechanics and complex systems. His best known contributions are the QCD evolution equations for parton den ...
and
Miguel Angel Virasoro in 1987
to solve some
mean field type models in
statistical physics
Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...
, specially adapted to disordered systems. The method has been used to compute properties of
ground states in many
condensed matter
Condensed matter physics is the field of physics that deals with the macroscopic and microscopic physical properties of matter, especially the solid and liquid phases which arise from electromagnetic forces between atoms. More generally, the sub ...
and
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s.
Initially invented to deal with the
Sherrington–Kirkpatrick model of
spin glass
In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magn ...
es, the cavity method has shown wider applicability. It can be regarded as a generalization of the
Bethe—
Peierls iterative method in tree-like graphs, to the case of a graph with loops that are not too short. The different approximations that can be done with the cavity method are usually named after their equivalent with the different steps of the
replica method which is mathematically more subtle and less intuitive than the cavity approach.
The cavity method has proved useful in the solution of
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s such as
k-satisfiability and
graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
. It has yielded not only ground states energy predictions in the average case, but also has inspired algorithmic methods.
See also
The cavity method originated in the context of
statistical physics
Statistical physics is a branch of physics that evolved from a foundation of statistical mechanics, which uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approxi ...
, but is also closely related to methods from other areas such as
belief propagation
A belief is an attitude that something is the case, or that some proposition is true. In epistemology, philosophers use the term "belief" to refer to attitudes about the world which can be either true or false. To believe something is to take i ...
.
References
Further reading
*
*
*
*
*
Condensed matter physics
{{CMP-stub