Customer Reviews

Models of Computation: Exploring the Power of Computing

5 star:		(1)
4 star:		(1)
3 star:		(0)
2 star:		(1)
1 star:		(0)

 

 

I get unceasing complaints about this text. The explanations are too shallow, the topics are too dense, and the author presents wonderful proofs with no explanation of what it is he is really trying to prove, or why the proof is important. To make matters worse, there are material errors in the text that impact the dicussion he presents. These errors make it nearly impossible to understand the underlying points he wants to make, and unfortunately there are many errors (for example, his whole discussion of CNF in Chapter 2. There are many others).
I think that when the author corrects these errors, and rewrites uncomprenhensible parts, this could be a good text. For now it is average at best, and I do not think it is ready to be used for classes, at least not at an undergraduate level.

This an introduction to complexity theory very different from Hopcroft and Ullman's book. It has material on lower-bound methods for circuit complexity, space-time tradeoffs (and VLSI area-time tradeoffs) and memory-hierarchy tradeoffs, which I didn't know at all before opening this book. It also has a very nice explanation of the efficient parallel prefix circuit."

Here is a book that has it all: a complete summary of theoretical computer science; well organized, detailed proofs; and quite understandable for the novice. This book should become the standard in its field.