Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The nature of computation
Moore C., Mertens S., Oxford University Press, Inc., New York, NY, 2011. 1032 pp.  Type: Book (978-0-199233-21-2)
Date Reviewed: Mar 26 2012

If there were an encyclopedia of computational complexity, this would be the first--and perhaps only necessary--volume. The book contains more than 900 pages and covers a large number of deeply related subjects ranging from discrete mathematics to quantum computation.

The list of contents belongs to the field of computational complexity. The greatest value is that it is not a handbook of unrelated, very technical facts (the topic can quickly become very dense), but provides an extensive discussion about the subject. It proceeds from relatively traditional topics such as the complexity classes, the P versus NP question, and random walks to phase transitions, quantum computation, and the connections to pure math and physics. Several subsets of chapters can be used as a textbook for an undergraduate complexity course, and the book could easily cover two- or three-semester courses, with the more advanced topics perhaps suitable for graduate seminars.

Moore and Mertens took great care to think about the reader and included highlighted sections, examples, and exercises. Most important (and what makes it more valuable than other similar, although smaller, books) is that all of the math is wrapped within a context providing insights for both the mathematical and the nonmathematical reader.

Perhaps the only thing I can criticize is the title. The subject of the nature of computation is much larger than the subfield of computational complexity, although I acknowledge that this subfield is among the largest and most popular in theoretical computer science. I particularly enjoyed Section 7.6, “Computation Everywhere,” which discusses much of what I would have enjoyed to see further developed in the context of the ambitious title of the book.

The book is definitely delightful. Everyone interested in the topics it covers should get a copy.

Reviewer:  Hector Zenil Review #: CR140009 (1208-0778)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
General (F.0 )
Complexity Measures And Classes (F.1.3 )
Models Of Computation (F.1.1 )
Would you recommend this review?
Other reviews under "General": Date
From computing to computational thinking
Wang P.,  Chapman & Hall/CRC, Boca Raton, FL, 2015. 288 pp. Type: Book (978-1-482217-65-0)
Jan 3 2017
Matrix calculus for classical and quantum circuits
De Vos A., De Baerdemacker S.  ACM Journal on Emerging Technologies in Computing Systems 11(2): 1-11, 2014. Type: Article
Dec 17 2014
Computability: Turing, Gödel, Church, and beyond
Copeland B., Posy C., Shagrir O.,  The MIT Press, Cambridge, MA, 2013. 376 pp. Type: Book (978-0-262018-99-9)
Jan 27 2014

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy