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.