Jump to ContentJump to Main Navigation
Computational Complexity and Statistical Physics - Oxford Scholarship Online
Users without a subscription are not able to see the full content.

Computational Complexity and Statistical Physics

Allon Percus, Gabriel Istrate, and Cristopher Moore


Computer science and physics have been closely linked since the birth of modern computing. In recent years, an interdisciplinary area has blossomed at the junction of these fields, connecting insights from statistical physics with basic computational challenges. Researchers have successfully applied techniques from the study of phase transitions to analyze NP-complete problems such as satisfiability and graph coloring. This is leading to a new understanding of the structure of these problems, and of how algorithms perform on them. Computational Complexity and Statistical Physics will serve as ... More

Bibliographic Information

Print publication date: 2005 Print ISBN-13: 9780195177374
Published to Oxford Scholarship Online: November 2020 DOI:10.1093/oso/9780195177374.001.0001


Affiliations are at time of print publication.

Allon Percus, editor

Gabriel Istrate, editor

Cristopher Moore, editor

Show Summary Details

subscribe or login to access all content.



Part 1 Fundamentals

Chapter 1 Introduction: Where Statistical Physics Meets Computation

Allon G. Percus, Gabriel Istrate, and Cristopher Moore

Part 2 Statistical Physics and Algorithms

Chapter 4 Constraint Satisfaction by Survey Propagation

Alfredo Braunstein and Marc Mézard

Part 3 Identifying the Threshold

Chapter 9 The Phase Transition in the Random HornSAT Problem

Demetrios D. Demopoulos and Moshe Y. Vardi

Part 4 Extensions and Applications

End Matter