Description |
1 online resource (xvii, 985 pages) : illustrations |
Contents |
Prologue -- The basics -- Insights and algorithms -- Needles in a haystack : the class NP -- Who is the hardest one of all? : NP-completeness -- The deep question : P vs. NP -- The grand unified theory of computation -- Memory, paths, and games -- Optimization and approximation -- Randomized algorithms -- Interaction and pseudorandomness -- Random walks and rapid mixing -- Counting, sampling, and statistical physics -- When formulas freeze : phase transitions in computation -- Quantum computation -- Mathematical tools |
Summary |
The boundary between physics and computer science has become a hotbed of interdisciplinary collaboration. In this book the authors introduce the reader to the fundamental concepts of computational complexity and give in-depth explorations of the major interfaces between computer science and physics |
Bibliography |
Includes bibliographical references (pages 945-973) and index |
Notes |
Print version record |
Subject |
Computational complexity.
|
|
MATHEMATICS -- General.
|
|
Computational complexity
|
|
Komplexitetsteori.
|
Form |
Electronic book
|
Author |
Mertens, Stephan
|
ISBN |
9780191775079 |
|
019177507X |
|
9780191552762 |
|
0191552763 |
|