The Nature of Computation by C. Moore and S. Mertens, Oxford University Press (2009)
ca. 870 pages, 300 problems, 150 figures

This book is an introduction into the fundamental concepts of computational complexity. The authors go beyond the usual discussion of P, NP and NP-completeness to explain the deep meaning of the P vs. NP question. They discuss counting, randomized algorithms, and higher complexity classes. Additional chapters cover topics that are current hotbeds of interdisciplinary research, like phase transitions in computation, Monte Carlo algorithms, and quantum computing. The book explains many recent results which have not yet appeared in any textbook.

The entire book is written in an informal style that gives depth with a minimum of mathematical formalism, exposing the heart of the matter rather than belaboring technical details. It is accessible to graduate students, advanced undergraduates and scientists from other fields.

If you would like to get informed when new sample chapters are available, please send an email to mertens (at) ovgu.de.

• Leaflet from Oxford University Press.
• Table of Contents