Titel: Computational Complexity and Statistical Physics
Herausgegeben von Allan Percus, Gabriel Istrate, Cristopher Moore
OXFORD UNIV PR
Februar 2006 - gebunden - 384 Seiten
This Santa Fe Institute volume is intended to be a standard reference to statistical physics methods in computer science theory, particularly in relation to the study of phase transitions in combinatorial problems. It will contain both basic pedagogical material and technical tips and discussions to review the field from a broad perspective. The study of phase transitions in combinatorial problems originated about 50 years ago in work on random graphs by Eros and Renyi. During the past 10 years, there has been increasing appreciation of the relevance of phase transitions to algorithmic performance on computationally hard problems. Mathematicians, computer scientists and physicists have been working to develop the theoretical tools to understand the processes fundamental to computation. This book should appeal strongly to the interdisciplinary group of information scientists.
Preface ; Part 1: Fundamentals ; 1. Introduction: Where Statistical Physics Meets Computation ; 2. Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics ; Part 2: Statistical Physics and Algorithms ; 3. Analyzing Search Algorithms with Physical Methods ; 4. Constraint Satisfaction by Survey Propagation ; 5. The Easiest Hard Problem: Number Partitioning ; 6. Ground States, Energy Landscape and Low-Temperature Dynamics of plus/minus Spin Glasses ; Part 3: Identifying the Threshold ; 7. The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements ; 8. Proving Conditional Randomness Using the Principle of Deferred Decisions ; 9. The Phase Transition in the Random HornSAT Problem ; Part 4: Extensions and Applications ; 10. Phase Transitions for Quantum Search Algorithms ; 11. Scalability, Random Surfaces and Synchronized Computing Networks ; 12. Combinatorics of Genotype-Phenotype Maps: An RNA Case Study ; 13. Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey ; Bibliography ; Index
Cristopher Moore is an Associate Professor at the University of New Mexico, and holds a joint appointment in the Computer Science and Physics departments. He received his Ph.D. in Physics from Cornell University in 1991. He has published 80 papers at the interface between these two fields, on topics ranging from statistical physics and phase transitions to quantum algorithms and mapping the internet.
"This volume provides a comprehensive overview of an exciting new research area at the interface between statistical physics and computer science. It is an excellent exposition, featuring state-of-the-art contributions by renowned researchers in the field. The book will serve as a useful reference for years to come." Bart Selman, Cornell University