4 ms·
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.
- gcv 18y agoThe 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 agoYes, 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 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.
- Mapou 18y agoNot 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 agoBlog of a quantum computing theorist: http://www.scottaaronson.com/blog/ 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_Description.pdf 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/ http://www.cs.princeton.edu/theory/complexity/ PRIMES is in P (famous paper): http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf http://www.math.princeton.edu/~annals/issues/2004/Sept2004/A...
- rms 18y agohttp://www.complexitytheory.com/ 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/ 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/discretemath/ http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/di...
- YuriNiyazov 18y agoThe solution manual to Sipser's first edition is available through bootleg bittorrent trackers, which makes it good for self-study.
- fbellomi 18y agoI would suggest "Computational Complexity" by C.H. Papadimitriou Great material, great exercises, very good bibliography
- ulvund 18y agoAs others said: Introduction to the Theory of Computation, by Michael Sipser Together with Shai Simonson's lectures: http://aduni.org/courses/theory/ http://aduni.org/courses/theory/
- keefe 18y agoThe definitive algorithms book is Cormen : http://projects.csail.mit.edu/clrs/ 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-Computer-Science/6-046JFall-2005/CourseHome/ 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-Manber/dp/0201120372 http://www.amazon.com/Algorithms-Creative-Approach-Udi-Manbe... this is also very good
- dangoldin 18y agoIf 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.