COMPUTATIONAL COMPLEXITY AND STATISTICAL PHYSICS

Computer science and physics have been closely linked sincethe birth of modern computing. In recent years, aninterdisciplinary area has blossomed at the junction ofthese fields, connecting insights from statistical physicswith basic computational challenges. Researchers havesuccessfully applied techniques from the study of phasetransitions to analyze NP-complete problems such assatisfiability and graph coloring. This is leading to a newunderstanding of the structure of these problems, and of howalgorithms perform on them.Computational Complexity and Statistical Physics willserve as a standard reference and pedagogical aid tostatistical physics methods in computer science, with aparticular focus on phase transitions in combinatorialproblems. Addressed to a broad range of readers, the bookincludes substantial background material along with currentresearch by leading computer scientists, mathematicians, andphysicists. It will prepare students and researchers fromall of these fields to contribute to this exciting area.