Phase Transitions, Computational Complexity and Computational Cliffs

This page gives an introduction to the concepts of phase transitions and the associated computational costs. The intention is for this page to be relatively self-contained; there are also many other more advanced pages and papers available elsewhere (related links).

Phase Transitions

Phase Transitions in Physical Systems

Take a bucket of water and start cooling it. At first nothing much seems to happen, it stays fluid, but then at a particular and very sharply defined temperature there is a dramatic change in its properties; it freezes and becomes solid. Once frozen then further cooling does not lead to any other such dramatic change.

This phenomenon, where a property of a system does a dramatic change at a particular value of a control parameter is called a "phase transition". The name phase refers to a particular state; in the case of H₂O "water" is one phase, and "ice" another, and the control parameter is "temperature".

Although very familiar, such a dramatic change of properties of the water might be considered rather strange: if you look at how water molecules interact at the molecular level there is nothing particularly special about the temperature of 0°C/32°F. What is also noteworthy is the sharpness of the transition. Water at -0.0001°C acts totally different from water at +0.0001°C. Put another way, suppose we take a sample of H₂O molecules, and ask the question

Does the sample act like a solid?

Firstly, practically, the answer is never "sort of". The answer depends on the temperature, and changes from "yes" to "no" instantaneously (in terms of temperature). Such a behavior is also be called a "threshold", marking the onset of a "almost certainly yes" answer to some question.

Secondly, the position (temperature) of the transition does not change between samples; all samples of water behave in this way.

Less obvious is that the the sharpness of the transition is a consequence of the very large number of water molecules in any visible piece of water/ice. If you took a small number of water molecules then the change would not be sudden but instead a smooth change happening over a range of temperatures. That is, the phase transition is a statistical effect. With water there is a small chance that even if at temperature where normally liquid it could act briefly like a solid, but the number of molecules in any visible sample of water is so large that the chance of this happening is so small that it would essentially never happen.

Not all materials have sharp phase transitions. For example, consider glass, as you heat it up then it gradually softens and does not exhibit the same rapid change from solid to liquid, instead changing from a very viscous liquid (flows slowly) to a less viscous liquid (flows easily).

Phase Transitions in Computer Science

Phase transitions are most familiar from physics but they can also arise in the artificial problems of computer science.

Decision problems

It is most easy to see the role of phase transitions in computer science if we first look at simple decision problems, that is, problems requiring a simple yes or no answer. Suppose we take the relevant problem instance and phrase the decision problem in the form

Does the problem instance have property P?

where the property P is chosen to match the relevant decision problem. For example, in a scheduling problem property P might be "have a legal schedule of less than 30 days".

Now suppose that we have access to many problem instances of arbitrary sizes, with many instances available at each size, but with the instances controlled by a parameter, a, that plays a role similar to the temperature.

If we take many instances at fixed but large size but with many values of the parameter a then we often find a behavior similar to the "finite size" line below

finite size vs. infinite size thresholds

That is, for a whole range of values of a the answer is "probably does not have P", for a different range the answer is "almost certainly has P", and there is a relatively sharp "phase transition region" between these two regions (phases).

Also, if we repeat the experiment at different sizes we can find the transition becomes sharper for larger sizes. In the limit of infinite size the transition can become a true threshold; there exists a critical value a_C that divides the region of "almost certainly has P" from the region of "almost certainly does not have P".

If this still seems mysterious then take a look at the "Buckets and Balls Problem" which is a very simple example exhibiting many of the properties of a phase transition.

Hence, knowing the value of a for an instance (and knowing which set of instances it came from) means that we can make a good prediction as to whether or not it has the property P. This is of interest as it can often be more time-consuming to measure P that it is to measure a.

Phase Transitions and Computational Complexity

So far we have only considered the answer to questions such as

Does the problem instance have property P?

However, typically, we also care about ask how long it takes to compute this answer.

The easy-hard-easy transition

Suppose that we experimentally find the average time needed to find a solution, or prove one does not exist, as we vary the control parameter. For hard problems, the typical behavior typically looks like: easy-hard-easy transition

that is, the problems are hardest in the phase transition region and easier elsewhere. When we are far from the phase transition region it is much easier to demonstrate that the instance has the property P, or prove that it doesn't.

As an example, consider scheduling problems, and suppose that a is some measure of the total number of tasks to be completed before some specified deadline. If the number of tasks is small then it is easy to find a schedule that meets the deadline. If the number of tasks is large then it is easy to demonstrate that it is impossible to complete them all before the deadline. the problem only becomes very hard at intermediate values for which it is is not immediately clear whether or not the deadline can be met.

However, we should note that not all thresholds are associated with (exponentially) hard problems, or an easy-hard-easy transition. Examples:

Random 2SAT has a clear and sharp threshold but all instances are solvable in polytime
Whether or not a random graph has a Hamiltonian cycle also has a clear threshold with no hard problems (assuming we use a reasonable algorithm). This is despite the fact that Hamiltonian cycles are NP-hard to find in general. The easiness of the transition is reasonable on the grounds that such graphs almost always have a Hamiltonian cycle if and only if they are double connected (that is, there exist two distinct paths between any two points), and that determining double-connectedness is also not hard.

Connecting Phase Transitions with Optimization

The basic idea is to regard the quality demanded of a solution in an optimization problem with the control parameter a in phase transition issues. For example, for scheduling problems we might try to maximize the number of tasks that can be completed before a specified deadline.

Typical behaviors for a single instance -- the computational cliff

Suppose we are doing optimization with a single instance and measure how long it takes to either achieve a given solution quality, or to prove that the desired solution quality is unachievable. The behavior will typically look somewhat like: computational cliff

that is, it is relatively easy to find solution with low quality, or to prove that solutions with unrealistically high qualities do not exist, but that these tasks get much harder as we approach optimal quality. The gap between the satisfiable and unsatisfiable lines arises because it is typically much easier to find the optimal solution than to prove that it is optimal (that is, to prove that a theory with any higher solution quality is unsatisfiable).

It is easy to see how such cliffs can give rise to the easy-hard-easy transition above. Suppose that we have many instances each with their own computational cliff, and furthermore that the instances are sufficiently similar (on average) that most of the cliffs occur at about the same value of a. Then on averaging over the cliffs from all the instances the cliffs from each instance are likely to overlap sufficiently in order to give the hard peak at the average position of cliff.

Back to project home page: http://www.cirl.uoregon.edu/ANTS/

Page last modified: 2000-09-05 by Andrew Parkes