Computational Complexity and Statistical PhysicsAllon Percus, Gabriel Istrate, 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 a standard reference and pedagogical aid to statistical physics methods in computer science, with a particular focus on phase transitions in combinatorial problems. Addressed to a broad range of readers, the book includes substantial background material along with current research by leading computer scientists, mathematicians, and physicists. It will prepare students and researchers from all of these fields to contribute to this exciting area. |
Contents
IDENTIFYING THE THRESHOLD | 23 |
Perspectives | 25 |
Analyzing Search Algorithms with Physical Methods | 63 |
Constraint Satisfaction by Survey Propagation | 107 |
Number Partitioning | 125 |
Ground States Energy Landscape and LowTemperature | 141 |
Techniques Behind | 159 |
Proving Conditional Randomness using The Principle | 179 |
Other editions - View all
Computational Complexity and Statistical Physics Allon Percus,Gabriel Istrate,Cristopher Moore Limited preview - 2006 |
Computational Complexity and Statistical Physics Allon Percus,Gabriel Istrate,Cristopher Moore Limited preview - 2006 |
Computational Complexity and Statistical Physics Allon Percus,Gabriel Istrate,Cristopher Moore Limited preview - 2006 |
Common terms and phrases
2-clauses analysis approximation asymptotic average backtracking belief propagation Boolean circuits Boolean function chapter clusters computational complexity Computer Science configuration consider constraint satisfaction problems constraints corresponding defined denote density differencing discrete distribution DPLL dynamics edges equations example exponentially factor graph figure finite fraction Friedgut function node given graph coloring graph properties Hamming distance heuristic hypergraph independent set inequality input instances integer k-SAT Kalai linear literals mathematical method monotone Boolean function NP-complete NP-hard number of steps parameters PDES scheme perfect partitions periodically specified phase transition Phys plaquette polynomial probabilistic probability of satisfiability PRWSAT Psoln random 3-SAT random graph ratio satisfiability problems search algorithms search tree sequence sharp threshold simulations solution solve spin glass statistical physics structure subsets survey propagation theorem theory threshold behavior threshold interval truth assignment UNSAT unsatisfied clauses upper bound vertex vertices XORSAT
Popular passages
Page 322 - M. Bellare, O. Goldreich and M. Sudan. Free Bits, PCPs and NonApproximability - Towards Tight Results.