Ask HN: Good books on computational complexity?

https://news.ycombinator.com/item?id=240408

by globalrev • 18 years ago

16 9 18 years ago

news.ycombinator.com

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.

gcv• 18 years 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• 18 years 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.

rw• 18 years 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• 18 years 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• 18 years ago

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

fbellomi• 18 years ago

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

Great material, great exercises, very good bibliography

ulvund• 18 years 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• 18 years 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• 18 years 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.

Ask HN: Good books on computational complexity?

Related Stories