Programming Books C Java PHP Python Learn more Browse Programming Books
  • List Price: $151.80
  • Save: $131.05 (86%)
Rented from apex_media
To Rent, select Shipping State from options above
Due Date: Dec 19, 2014
FREE return shipping at the end of the semester. Access codes and supplements are not guaranteed with rentals.
Used: Good | Details
Sold by apex_media
Condition: Used: Good
Comment: Ships direct from Amazon! Qualifies for Prime Shipping and FREE standard shipping for orders over $25. Overnight and 2 day shipping available!
Access codes and supplements are not guaranteed with used items.
Add to Cart
Qty:1
  • List Price: $151.80
  • Save: $34.51 (23%)
Only 3 left in stock (more on the way).
Ships from and sold by Amazon.com.
Gift-wrap available.
Add to Cart
Trade in your item
Get a $8.77
Gift Card.
Have one to sell? Sell on Amazon
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See this image

Computational Complexity Paperback – December 10, 1993

ISBN-13: 978-0201530827 ISBN-10: 0201530821 Edition: 1st

Buy New
Price: $117.29
Rent
Price: $20.75
28 New from $86.66 37 Used from $23.38
Rent from Amazon Price New from Used from
Hardcover
"Please retry"
$69.50
Paperback
"Please retry"
$20.75
$117.29
$86.66 $23.38

Free%20Two-Day%20Shipping%20for%20College%20Students%20with%20Amazon%20Student



Frequently Bought Together

Computational Complexity + Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science)
Price for both: $132.11

Buy the selected items together

NO_CONTENT_IN_FEATURE

Shop the new tech.book(store)
New! Introducing the tech.book(store), a hub for Software Developers and Architects, Networking Administrators, TPMs, and other technology professionals to find highly-rated and highly-relevant career resources. Shop books on programming and big data, or read this week's blog posts by authors and thought-leaders in the tech industry. > Shop now

Product Details

  • Paperback: 523 pages
  • Publisher: Addison-Wesley; 1 edition (December 10, 1993)
  • Language: English
  • ISBN-10: 0201530821
  • ISBN-13: 978-0201530827
  • Product Dimensions: 9.5 x 6.6 x 1.1 inches
  • Shipping Weight: 1.9 pounds (View shipping rates and policies)
  • Average Customer Review: 3.9 out of 5 stars  See all reviews (18 customer reviews)
  • Amazon Best Sellers Rank: #686,970 in Books (See Top 100 in Books)

Editorial Reviews

From the Back Cover

This new text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, parallel computation, the polynomial hierarchy, and many others.

Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse field as computability, logic, number theory, combinatorics, and probability.

Features
  • First unified introduction to computational complexity.
  • Integrates computation, applications, and logic throughout.
  • Provides an accessible introduction to logic, including Boolean logic, first-order logic, and second-order logic.
  • Includes extensive exercises including historical notes, references, and challeging problems.


0201530821B04062001


More About the Author

Christos Papadimitriou was born and raised in Athens, Greece, and studied in Athens and at Princeton. He has taught Computer Science at Harvard, MIT, Stanford, and, since 1996, at Berkeley, where he is the C. Lester Hogan Professor of Computer Science. In his research he uses mathematics to understand the power and limitations of computers. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has written several of the standard textbooks in algorithms and computation, and two novels: "Turing" and "Logicomix" (with Apostolos Doxiadis, art by Alecos Papadatos and Annie di Donna). He is working on his third novel, "Independence."


Customer Reviews

3.9 out of 5 stars
5 star
8
4 star
6
3 star
1
2 star
0
1 star
3
See all 18 customer reviews
Sci., not the 3rd IEEE Symp. on Found. of Comp.
Arthur Fischer
I would recommend this book to anyone interested in the field of complexity theory.
susavisa
IMO, this book covers so many topics, that it becomes too dense to read.
Li Ping Chou

Most Helpful Customer Reviews

16 of 17 people found the following review helpful By A Customer on July 2, 1997
Format: Paperback
By far, the best book on complexity theory that I have ever read. I disagree with another reviewer's assessment of a lack of feasibility issues; that's not the focus of this book, nor should it be the focus of any book on complexity theory.
Papadimitriou's proofs are complete, concise, and understandable, which is more than I can say for most books on the subject. If you are interested in an in-depth coverage of a wide range of topics relating to complexity theory, this book is an excellent starting point. Highly recommended
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
46 of 56 people found the following review helpful By Arthur Fischer on August 22, 2000
Format: Paperback
I used this book for a reading course in Complexity Theory. In going through the text, I found that though most topics were introduced in a fairly thorough manner, with enough axamples to make them understabdable, sometimes Papadimitriou would make some fairly simple mistakes. Of course, hese mistakes may be seen as typos in many places, but the sheer volume of them is difficult to attribute to typos alone. The readability of a proof, or a solution to an example is greatly reduced with the presence of inconsistent notations, and plain mathematical garbage.
The set of references and notes listed at the conclusion of most chapters was excellent, but the reader is to beware that some of the references listed are wrong (Cook's Theorem is from the 3rd ACM Symp. on Found. of Comp.Sci., not the 3rd IEEE Symp. on Found. of Comp. Sci., for instance).
These problems make it difficult for the comitted learner to get all the information he/she wants, and greatly detracted from my enjoyment of the text.
Unfortunately, I am unable to direct people to a more consistent text in Complexity Theory suitable for the senior undergrad through graduate levels.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
11 of 13 people found the following review helpful By Li Ping Chou on June 2, 2003
Format: Paperback
Yes,it is generally "hard" for undergradute students even grad. students. If you are taking course "Theory of computation", I would like to recommend the Sipser's or Cohen's books for reading supplement. But you should keep reading this book ! IMO, this book covers so many topics, that it becomes too dense to read. It means you should read it carefully and slowly. For example, it introduces the "reduction" in some previous chapters but without precise defintion and therefore misses the more important part :how to do the reduction correctly and what is the "reseasonable" reduction ? You will find the concept of "reduction" is not very easy to catch if you refer to the Sipser's or Ullman's books. Many friends and me could not go through more than 20 pages of this book in the beginning. But we were keeping on reading and surveying some "easy books". Finally, we understood most half parts of this book. Moreover, if some readers prepare to study more advanced and recent topics, this book is the must.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
13 of 17 people found the following review helpful By Todd Ebert on September 14, 2000
Format: Paperback
Papadimitriou is one of the great minds in computer science, which is reflected in this gem of a book. His prose is very engaging and he covers just about every topic (although be it lightly) relevant in modern complexity theory without overly diluting the proofs and results (for example, he gives a nice concise proof of Razborov's theorem on monotone circuits).
1 Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
15 of 20 people found the following review helpful By Mugizi R. Rwebangira on April 29, 2003
Format: Paperback Verified Purchase
I found this book hard to follow. However, I suspect I did not have the strong background in complexity theory required by it.
This probably should not be the first book you read on this subject.
It is a dense book and will probably reward intense study.
Also I think it is a good reference as it discusses most of the important complexity classes out there.
The only problem is that I think it is slightly outdated by now, being published in 1994 and hence does not contain much discussion of the latest results especially on inapproximability, the PCP theorem and so on.
However, this is THE standard text on complexity theory and many people swear by it, which is why I still give it 5 stars.
2 Comments Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
3 of 3 people found the following review helpful By Yuanchyuan Sheu on February 16, 2009
Format: Paperback
We used this book for one semester when I was in the graduate school. This is one of the computer science related books that actually have enough substance to have some intellectual value.

I found this volume entertaining years after leaving graduate school and working in the industry as an engineer. The topics addressed in this book is actually quite intriguing--the best time to reduce programming complexity is before one actually programs. I believe any serious programmer should be able to estimate the complexity, both space and time, on the algorithm he is designing.

In the real world, one does not encounter nontrivial algorithms very often, and from a practical perspective, this books is not quite useful.

However, when you really get bored, this is something that could entertain your brain a little.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
5 of 6 people found the following review helpful By W. Ghost on November 2, 2007
Format: Paperback Verified Purchase
This book is excellent. However, you need strong training in the kind of reasoning used in math and CS theory before you can read it. The subject gets very abstract, and may be hard to follow (and that's not Papadimitriou's fault).

I would recommend it for people who have already read Sipser's book (working on the exercises), for example.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
4 of 5 people found the following review helpful By Amazon Customer on May 5, 2002
Format: Paperback
As an undergraduate computer science student studying theory, I found this book facinating and helpful. It clearly explained the primary concepts of complexity. The theorems are useful and the proofs are fairly straightforward. All in all, an interesting read. He spends a little bit too much time on logic, and his proof of Rice's theorem is a bit odd, but all in all this is a great book.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again

Most Recent Customer Reviews

Search

What Other Items Do Customers Buy After Viewing This Item?