Computational Complexity

by Christos H. Papadimitriou

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 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.

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

Hardcover

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.