|
Computational Complexity
 |
Author: Christos H. Papadimitriou
List Price: $61.00
Our Price: Click to see the latest and low price
ISBN: 0201530821
Publisher: Addison-Wesley Pub Co (30 November, 1993)
Edition: Hardcover
Sales Rank: 62,852
Average Customer Rating: 3.92 out of 5
|
Customer ReviewsRating: 4 out of 5
Good overall.
A well-written book that teaches you how to think about complexity theory instead of just a flat summary of results. Something like Lewis and Papadimitriou's _Elements of the Theory of Computation_ would be more than enough preparation for this (note that the style of these books is quite different- this one is more informal and descriptive). Covers all the material you need in a first text. Has a good little introduction to mathematical logic in it, including a nice succinct version of Godels Incompleteness Theorem. Lots of interesting exercises.
Rating: 4 out of 5
Understanding The Mad Chronic Sacks Of Phat Buds
*Computational Complexity* is a great introduction to contemporary formal logic, which is more heavily mathematical than even the great mathematical logicians of the past were. It's a great introduction, even though they put a good-lookin' chick on the *back* cover (what's that about?), because Papadimitriou does not suffer from what Quine called *mathematosis* -- he is not assimilating the material of logic (anything and everything symbolic) to the rigorized abstractions of mathematics. And as such, this book defines what I think *computer science* should be today by choosing the "greater of two evils". If you think that computer science began with Turing like most people, CS is about building machines that do what thinking beings do (problems of detail); but if you think that computer science began with Church's undecidability theorem, CS would be about figuring out why thinking beings fall down on the reasoning job (troubles with principle). I prefer the second definition; and although I'm a little old-fashioned in my tastes (prove it by me), this book demonstrates such an attitude can be forward-looking. Although Church is not venerated throughout the book, a task handled by Papadimitriou in his earlier CS introduction with Lewis, unlike Hopcroft and Ullman the spirit of Church is very much present in Papadimitriou's teasing-apart of complexity problems from applied CS. Yes, it's never about the physical machine, and Ryle can go away instead of work like this -- which in my opinion could form the basis of a "computational psychology" concerned with the will to truth rather than the will to power.
Rating: 1 out of 5
All in one roof, but presentation very poor
I agree with the review by Arthur Fischer. Papadimitriou might
be an excellent researcher, but his communication skills are
hopeless and horrible. The typos make learning even harder.Perhaps someone like Michael Sipser should take up the task of
rewriting this book.
Similar Products
· Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)
· Randomized Algorithms
· Introduction to the Theory of Computation
· Introduction to Algorithms, Second Edition
|
