Description 
1 online resource (xiii, 367 pages) : illustrations 
Series 
Santa Fe Institute studies in the sciences of complexity 

Proceedings volume in the Santa Fe Institute studies in the sciences of complexity.

Contents 
Where statistical physics meets computation / Allon G. Percus, Gabriel Istrate, and Cristopher Moore  Threshold phenomena and influence : perspectives from mathematics, computer science, and economics / Gil Kalai and Shmuel Safra  Analyzing search algorithms with physical methods / Simona Cocco [and others]  Constraint satisfaction by survey propagation / Alfredo Braunstein [and others]  The easiest hard problem : number partitioning / Stephan Mertens  Ground states, energy landscape, and lowtemperature dynamics of ±J spin glasses / Sigismund Kobe and Jarek Krawczyk  The satisfiability threshold conjecture : techniques behind upper bound improvements / Lefteris M. Kirousis, Yannis C. Stamatiou, and Michele Zito  Proving conditional randomness using the principle of deferred decisions / Alexis C. Kaporis, Lefteris M. Kirousis, and Yiannis C. Stamatiou  The phase transition in the random hornSAT problem / Demetrios D. Demopoulos and Moshe Y. Vardi  Phase transitions for quantum search algorithms / Tad Hogg  Scalability, random surfaces, and synchronized computing networks / Zoltan Toroczkai [and others]  Combinatorics of genotypephenotype maps : an RNA case study / Christian M. Reidys  Towards a predictive computational complexity theory for periodically specified problems : a survey / Harry B. Hunt III [and others] 
Summary 
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 NPcomplete 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 
Bibliography 
Includes bibliographical references (pages 319351) and index 
Notes 
Print version record 
Subject 
Combinatorial analysis.


Computational complexity.


Phase transformations (Statistical physics)


Statistical physics.

Genre/Form 
Kongress.


Santa Fe (NM, 2001)

Form 
Electronic book

Author 
Istrate, Gabriel.


Moore, Cristopher.


Percus, Allon.

ISBN 
019976056X (electronic bk.) 

1283097850 

9780199760565 (electronic bk.) 

9781283097857 
