Ask HN: Good books on computational complexity? | Hacker News Reader

Ask HN: Good books on computational complexity?

16 pointsglobalrev9 comments

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.

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.

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.

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

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

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

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

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.

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

Great material, great exercises, very good bibliography

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

Together with Shai Simonson's lectures:

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

Reply on news.ycombinator.com