Ask HN: Good books on computational complexity?

I am curious about computational complexity, P, NP and so on.

Wikipedia gives a good basic insight but doesn't go very deep.

What books do you recommend? Plus points for one that discusses how parallelism fits into this.

10 comments

[ 3.5 ms ] story [ 23.8 ms ] thread

gcv 18y ago ↗

The best book on the subject I know of is Introduction to the Theory of Computation, by Michael Sipser. Very readable and lucid. Great exercises.

neilc 18y ago ↗

Yes, definitely the best introductory book on the subject I've ever seen. Indeed, the Sipser book is a model for how to write a very readable, accessible CS theory textbook.

As far as how complexity theory on parallel computing, communication complexity is one related approach:

http://en.wikipedia.org/wiki/Communication_complexity

which provides a rigorous way to characterize how much communication is inherently required to solve a particular problem.

[dead] Mapou 18y ago ↗

Not to discourage your perfectly valid interest in this subject but I am curious about the percentage of software engineers that use any knowledge of computational complexity in their everyday work.

rw 18y ago ↗

Blog of a quantum computing theorist: http://www.scottaaronson.com/blog/

P vs NP Millenium Prize intro paper, which is fairly accessible: http://www.claymath.org/millennium/P_vs_NP/Official_Problem_...

Complexity Theory: A Modern Approach (out of Princeton): http://www.cs.princeton.edu/theory/complexity/

PRIMES is in P (famous paper): http://www.math.princeton.edu/~annals/issues/2004/Sept2004/A...

rms 18y ago ↗

http://www.complexitytheory.com/

Edit: The lectures don't seem to be up there anymore but he links to this book which is free online pre-publication: http://www.cs.princeton.edu/theory/complexity/

Rudich's lectures are up for his undergrad class though, http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/di...

YuriNiyazov 18y ago ↗

The solution manual to Sipser's first edition is available through bootleg bittorrent trackers, which makes it good for self-study.

fbellomi 18y ago ↗

I would suggest "Computational Complexity" by C.H. Papadimitriou

Great material, great exercises, very good bibliography

ulvund 18y ago ↗

As others said: Introduction to the Theory of Computation, by Michael Sipser

Together with Shai Simonson's lectures:

http://aduni.org/courses/theory/

keefe 18y ago ↗

The definitive algorithms book is Cormen : http://projects.csail.mit.edu/clrs/ I think you should study this book and here is the MIT course to go along with it : http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...

Learning about NP complete problems is interesting to avoid certain pitfalls and mapping one problem to another is always a valuable technique, but it seems you are fairly new to analysis of algorithms so imho (having been a phd student focused on algorithms) this book and course is a great place to start.

http://www.amazon.com/Algorithms-Creative-Approach-Udi-Manbe...

this is also very good

dangoldin 18y ago ↗

If you are in the mood for something advanced, take a look at Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman.

It has a good amount of proofs and a pretty strong focus on automata thought so that may not be your cup of tea.

Hopcroft won the Turing award in 1986 so he knows what he's talking about.