Computational complexity and statistical physics / editors, Allon G. Percus, Gabriel Istrate, Cristopher Moore.

Format:

Book

Contributor:

Percus, Allon.

Istrate, Gabriel.

Moore, Cristopher.

Series:

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

Santa Fe Institute studies in the sciences of complexity

Language:

English

Subjects (All):

Computational complexity.

Combinatorial analysis.

Statistical physics.

Phase transformations (Statistical physics).

Physical Description:

xiii, 367 pages : illustrations ; 24 cm.

Place of Publication:

Oxford ; New York : Oxford University Press, 2006.

Summary:

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.

Notes:

Includes bibliographical references (pages 319-351) and index.

ISBN:

0195177371

019517738X

OCLC:

59279852

Publisher Number:

9780195177374

9780195177381