ABSTRACT
The origin of the applications of statistical mechanics to diverse "complex systems" lies mainly in the development of spin glass theory. This chapter presents a short summary of the relevant parts of statistical mechanics. It describes two types of statistical mechanics approaches that can and have been used in combinatorial problems: simulated annealing, and various analytical approaches. Application to complex optimization problems has occurred in parallel with applications to neural networks, "real" glasses, dynamics and folding of biomolecules, and prebiotic evolution. Combinatorial optimization problems studied in computer science and operations research share many of the features of spin glasses. There are many qualitative and quantitative properties of landscapes that are relevant to algorithm design for rough cost surfaces. Adopting a landscape viewpoint, or more generally considering the topology of the configuration space, was a crucial step in understanding spin glasses.
