The Nature of Computation

Computational complexity is one of the most beautiful fields ofmodern mathematics, and it is increasingly relevant to othersciences ranging from physics to biology. But this beauty is oftenburied underneath layers of unnecessary formalism, and excitingrecent results like interactive proofs, phase transitions, andquantum computing are usually considered too advanced for thetypical student. This book bridges these gaps by explaining thedeep ideas of theoretical computer science in a clear and enjoyablefashion, making them accessible to non-computer scientists and tocomputer scientists who finally want to appreciate their field froma new point of view. The authors start with a lucid and playfulexplanation of the P vs. NP problem, explaining why it is sofundamental, and so hard to resolve. They then lead the readerthrough the complexity of mazes and games; optimization in theoryand practice; randomized algorithms, interactive proofs, andpseudorandomness; Markov chains and phase transitions; and theouter reaches of quantum computing. At every turn, they use aminimum of formalism, providing explanations that are both deep andaccessible. The book is intended for graduate and undergraduatestudents, scientists from other areas who have long wanted tounderstand this subject, and experts who want to fall in love withthis field all over again.First published 2011Reprinted 2012, 2013 (with corrections), 2014 (with corrections),2016 (twice, once with corrections), 2017 (with corrections)