14 - The physics of complexity

Summary

Spin glass theory has had a rather large and unexpected impact on some problems far removed from spin glasses themselves. It turns out that a number of problems in fields outside physics share some of the essential features — randomness and frustration — that characterize spin glasses, and insights and techniques can be borrowed from spin glass theory and brought usefully to bear on them. This is especially true of the special novel concepts of mean field theory: broken ergodicity is a fundamental concept and broken replica symmetry may be a basic tool for analysing complex systems. While these methods probably do not apply to real spin glasses, many of these other problems have effectively infinite-ranged interactions, and mean field theory (sometimes with replica symmetry breaking) is applicable to them.

In the long run, these problems, rather than spin glasses themselves, may be the reason for reading the first part of this book. The hope that understanding spin glasses could be a key that unlocks the secrets of many other complex systems in and out of physics has been an important factor in making spin glass theory such an active field in the last decade.

In this chapter we describe a few representative examples of such problems. We will examine first some combinatorial optimization problems, in particular, the weighted matching, ‘travelling salesman’, and graph bipartitioning problems. Then we will describe some of the recent progress in understanding collective computational networks.