Matter commonly undergoes dramatic changes in its qualitative properties when certain parameters pass through particular values. A common everyday example is the melting of a solid with increasing temperature, a parameter that characterizes the average energy available to the atoms making up the solid. As temperature increases the atomic vibrations become gradually more violent, leading to the well known phenomenon of thermal expansion. Since this increase in vibration amplitude is gradual, one would naively expect that the macroscopic properties of the substance would accordingly undergo a smooth change. While this is true over most of the temperature range, there exists a well defined temperature for which something much more dramatic happens: a sudden change in the properties of the substance over a small temperature range, and the appearance of a qualitatively different phase, in this case a liquid. This melting transition involves, among other things, an abrupt softening of the solid even though its average atomic energy changes only slightly. The ensuing liquid can in turn undergo another phase transition into a gas phase, where once again properties, such as the density, change discontinuously.

Other examples of phase transitions appear in magnets and
superconductors when heated, the creation of self-replicating
biochemicals above a certain reactive mass, and many other systems
composed of a large number of components. Of particular relevance to
search problems is the phase transition displayed by percolation
processes. They can be easily visualized by considering a network of
channels connecting sites and the water flow through these channels. An
important *local* parameter for such a network is the
average number of neighbors a site has. Given an initial concentration
of fluid in a single site and a pressure gradient, a typical problem
consists in determining *global* properties such as
how many sites, on the average, get wet after a long time, or the
probability that distant sites get wet. This percolation problem, which
has been extensively studied in contexts such as oil extraction, the
spread of epidemics, and the conductivity of electrical
networks [9, 10], has a phase
transition independent of the detailed geometry of the system.
Specifically, for infinitely large networks, when the average number of
neighbors is sufficiently small, there is unlikely to be any global flow
from one side of the system to the other, i.e., the probability of
finding a wet site at an arbitrarily large distance from the source is
vanishingly small. This means that only a finite number of sites are
connected to the source. As the number of neighbors increases however,
there is a value at which global flow becomes very likely, the
probability that distant sites get wet becomes nonzero, and the
connected cluster becomes infinite. Here the transition is characterized
by a jump in the derivative of this probability and global flow rate. At
the transition the global flow is nonzero, but small. Beyond this point
the global flow continues to increase. This behavior also corresponds to
thresholds in the cluster size of random graphs [2]. In these cases, the transition is less
dramatic than melting or boiling because the new behavior increases
gradually after the transition, but nevertheless the onset is still
abrupt.

These phase changes are characterized by the appearance of
*singularities* in observables such as
the density, viscosity and specific heat of matter or long range
connectivity in percolation. That is, at the transition, some global
behavior is not analytic, in the limit of infinitely large systems.
Depending on the nature of the transition, one might also observe
phenomena such as hysteresis, sluggish response to external stimuli, or
the nucleation of a new phase. Studies in statistical mechanics have
shown that despite the apparent diversity in the composition and
underlying structure of these systems, phase transitions take place with
universal quantitative characteristics, independent of the detailed
nature of the interactions between individual components. This means the
singular behavior of observables near the transition point is identical
for many systems when appropriately scaled, defining universality
classes that only depend on the range of interaction of the forces at
play and the dimensionality of the problem [14, 57]. One of these common
characteristics is rapidly increasing correlation lengths between parts
of the system as the transition is approached, giving rise to a change
from a disordered to an ordered state and particularly large variances.
It is these so-called ``critical phase transitions'' that are
most relevant to computational search.

This theoretical treatment of phase transitions relies on models that, in the limit of very many components, can be considered stochastic in nature, an approximation that works exceedingly well in characterizing their generic properties. In this so-called thermodynamic limit, extensive quantities such as the number of particles and the volume they occupy become infinitely large, while the average number per unit volume remains constant. Thus, strictly speaking, phase transitions only exist for infinitely large systems, but nevertheless give qualitative and quantitative insight to smaller cases, e.g., through the use of finite size scaling [33]. In particular, for finite systems, the transition is somewhat smoothed out.

Thu May 16 15:45:43 PDT 1996