Computational Complexity

by Christos H. Papadimitriou

This modern introduction to the Theory of Computer Science is the first unified introduction to Computational Complexity. It 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. The book is self-contained in that it develops all necessary mathematical prerequisites from such diverse fields such as computability, logic, number theory and probability.

Genres: Computer Science, Mathematics, Computers, Science, Nonfiction, Textbooks, Algorithms

523 pages, Paperback

First published December 10, 1993

About the author

Christos Harilaos Papadimitriou (Greek: Χρίστος Χ. Παπαδημητρίου) is a Professor in the Computer Science Division at the University of California, Berkeley, United States.
Papadimitriou is the author of the textbook Computational Complexity and has co-authored Algorithms with Sanjoy Dasgupta and Umesh Vazirani.
He has collaborated with Apostolos Doxiadis on the graphic novel Logicomix, and has published one novel, Turing.

Reviews

[Yousef · Rating 5 out of 5]

If you read this book as first time in order to understand Computational Complexity, then you're probably not going to like it. You need to read Sipser's textbook before you read this book and make sure that you have a strong background in discrete mathematics (if not, then see Rosen's textbook in Discrete Mathematics). This book is recommended by best people in complexity and algorithms such as Scott Aaronson, Sipser, etc. You need to solve as many exercises as you go.

The book has five parts:
Part I: Algorithms
Part II: Logic
Part III: P and NP
Part IV: Inside P
Part V: Beyond NP

The most important parts are in Part I, III.

[dead letter office · Rating 3 out of 5]

i'm not aware of too many choices for introductory graduate complexity theory. this one is not great, but it'll work.

[DJ]

recommended by Scott Aaronson as a conceptual intro to complexity

[Alex · Rating 5 out of 5]

Maybe the best math book I've ever read

[Daniel · Rating 3 out of 5]

I read some chapters of it last year, when I took a graduate computational complexity course. I found them someway hard to read. Readers should be aware of (mostly negligible) errors in some proofs. I think I should give a second chance to it in the first occasion.

[Frank Palardy · Rating 4 out of 5]

Used for class. Hard.