The instances which are the hardest to solve appear in the vicinity of the transition. Here, the problem is treated by means of computer simulations and analytical calculations. Usually the covers of random graphs are highly degenerate. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively replaces extremely undesirable elements of a single sub-optimal solution with new, random ones.
Large fluctuations ensue that efficiently explore many local optima.
With only one adjustable parameter, its performance has proved competitive with more elaborate methods, especially near phase transitions which are believed to contain the hardest instances. I will then discuss various well-known models in statistical physics from the standpoint of computational complexity, placing them in complexity classes based on the scaling of the computational resources required to simulate them. Computational complexity considerations are useful in designing simulations and, more fundamentally, computational complexity provides a new way of characterizing and classifying systems in statistical physics.