Buy used: $107.03

$3.99 delivery February 3 - 6. Details

Select delivery location

Used: Good | Details

Sold by Goodwill Gulf Coast

Access codes and supplements are not guaranteed with used items.

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

Follow the Author

Christos H. Papadimitriou

Computational Complexity 1st Edition

by Christos Papadimitriou (Author)

23 ratings

See all formats and editions

Price

New from

Used from

Paperback

"Please retry"

—

$626.99

Paperback, November 30, 1993

$107.03

—

$107.03

Paperback
$107.03

9 Used from $107.03

This 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 fields as computability, logic, number theory, combinatorics and probability.

ISBN-10

0201530821
ISBN-13

978-0201530827
Edition

1st
Publisher

Pearson
Publication date

November 30, 1993
Language

English
Dimensions

1.1 x 6.1 x 8.9 inches
Print length

523 pages
See all details

Sanjeev Arora
110
Hardcover
27 offers from $25.16
Christos H. Papadimitriou
89
Paperback
31 offers from $4.48
JOHN E. HOPCROFT ET AL
333
Paperback
59 offers from $14.49
Michael Sipser
474
Hardcover
28 offers from $64.48
Avi Wigderson
12
Hardcover
19 offers from $35.00
Michael R. Garey
52
Paperback
16 offers from $45.39

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

Product details

Publisher ‏ : ‎ Pearson; 1st edition (November 30, 1993)
Language ‏ : ‎ English
Paperback ‏ : ‎ 523 pages
ISBN-10 ‏ : ‎ 0201530821
ISBN-13 ‏ : ‎ 978-0201530827
Item Weight ‏ : ‎ 1.9 pounds
Dimensions ‏ : ‎ 1.1 x 6.1 x 8.9 inches

Best Sellers Rank: #1,891,634 in Books (See Top 100 in Books)
- #8,211 in Computer Science (Books)
- #22,702 in Mathematics (Books)

Customer Reviews:
23 ratings

Brief content visible, double tap to read full content.

Full content visible, double tap to read brief content.

Videos

Help others learn more about this product by uploading a video!

Upload your video

About the author

Follow authors to get new release updates, plus improved recommendations.

Christos H. Papadimitriou

Brief content visible, double tap to read full content.

Full content visible, double tap to read brief content.

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 three novels: "Turing," "Logicomix" (with Apostolos Doxiadis, art by Alecos Papadatos and Annie di Donna), and "Independence" (2017).

Customer reviews

4.3 out of 5

23 global ratings

5 star		66%
4 star		12%
3 star		18%
2 star 0% (0%)		0%
1 star		4%

How customer reviews and ratings work

Top reviews from the United States

There was a problem filtering reviews right now. Please try again later.

arthur

great book, unfortunately not well kept

Reviewed in the United States 🇺🇸 on November 15, 2022

Verified Purchase

why put barcode stickers directly on the cover? disrespectful treatment to own books..

Helpful

Smug

good book for beginners

Reviewed in the United States 🇺🇸 on October 25, 2007

Verified Purchase

This is a good introductory book of computational theory for students in computer science, good juniors, seniors and first year graduates. The book is well presented, fit for self studies, and covered most contents of computability and complexity. The book is slightly old, some of the latest result are not included, e.g., a P-algorithm of solving "prime problem" was found in 2001. This book is not good for advanced researchers in theoretical computer science, it is way to shallow. Compared with Martin Davis's book, this is easier to understand, equally well presented. Be sure not to get the $8-9 version, that is not the book, although under the same title.

I am a research in theoretical algorithms.

4 people found this helpful

Helpful

W. Ghost

Excellent book, but you need some training

Reviewed in the United States 🇺🇸 on November 3, 2007

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.

11 people found this helpful

Helpful

Amazon Customer

Four Stars

Reviewed in the United States 🇺🇸 on July 20, 2016

Verified Purchase

explains the concepts well

Helpful

susavisa

Excellent book in complexity theory

Reviewed in the United States 🇺🇸 on April 17, 2014

Verified Purchase

This is a great book on complexity theory at a graduate school level.
I would recommend this book to anyone interested in the field of complexity theory.

One person found this helpful

Helpful

Arthur Fischer

Good Information, Poorly Executed

Reviewed in the United States 🇺🇸 on August 22, 2000

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.

53 people found this helpful

Helpful

Yuanchyuan Sheu

Entertaining

Reviewed in the United States 🇺🇸 on February 17, 2009

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.

5 people found this helpful

Helpful

Jeffrey Rubard

The classic approach to complexity theory

Reviewed in the United States 🇺🇸 on December 8, 2003

[2016 review] Given the rapidity of technological development, the CS beginner may be surprised to learn that older textbooks contain much that is valuable: as with the rise of functional programming languages that derive their inspiration from Lisp, one of the first programming languages, there's a fair amount of "going back to the future". Christos Papadimitriou's *Computational Complexity* is a good illustration of this principle. Complexity theory is one of the most "scientific" parts of computer science, and with a $1 million prize (still) on offer for a solution to the P and NP problem there's no lack of attention to its basic concepts; recursive functions are well and good but if we want to do it on a computer, even a modern umpteen-core wonder, we need to be able to do it "fast". What budding computer scientists may lack is the logical background necessary to make sense of the complexity classes and what they mean for programming practice.

Papadimitriou is professor of logic at UC-Berkeley and a gifted expositor of logical concepts: he recently wrote the text for *Logicomix*, a graphic novel about the founding of modern logic in the early 20th century. What you will find in this decades-old text is the logic you need to understand computer science and the computer science you need to understand logic: not only the dedicated CS student, but philosophers and other people with "theoretical" interests in computational paradigms will benefit immensely from reading this (most "theory of computation" texts are designed to slingshot students into compiler construction and reinforce the principles of algorithms, so they leave out the negative result of the *Entscheidungsproblem* for first-order logic, the reason modern computation exists in the first place). The layout of the different complexity classes, beginning with the "tractable" P and going on into the well-named "complexity zoo", is explained in readable prose and understandable diagrams.

You need not be a genius to learn complexity from this book, only willing to be reflective about the principles of practices you know more "intuitively". Still relevant.

One person found this helpful

Helpful