I am curious about computational complexity, P, NP and so on.<p>Wikipedia gives a good basic insight but doesn't go very deep.<p>What books do you recommend?
Plus points for one that discusses how parallelism fits into this.
Blog of a quantum computing theorist:
<a href="http://www.scottaaronson.com/blog/" rel="nofollow">http://www.scottaaronson.com/blog/</a><p>P vs NP Millenium Prize intro paper, which is fairly accessible:
<a href="http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf" rel="nofollow">http://www.claymath.org/millennium/P_vs_NP/Official_Problem_...</a><p>Complexity Theory: A Modern Approach (out of Princeton):
<a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">http://www.cs.princeton.edu/theory/complexity/</a><p>PRIMES is in P (famous paper):
<a href="http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf" rel="nofollow">http://www.math.princeton.edu/~annals/issues/2004/Sept2004/A...</a>
<a href="http://www.complexitytheory.com/" rel="nofollow">http://www.complexitytheory.com/</a><p>Edit: The lectures don't seem to be up there anymore but he links to this book which is free online pre-publication: <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">http://www.cs.princeton.edu/theory/complexity/</a><p>Rudich's lectures are up for his undergrad class though, <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/discretemath/" rel="nofollow">http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/di...</a>
The definitive algorithms book is Cormen : <a href="http://projects.csail.mit.edu/clrs/" rel="nofollow">http://projects.csail.mit.edu/clrs/</a>
I think you should study this book and here is the MIT course to go along with it : <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/" rel="nofollow">http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...</a><p>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.<p><a href="http://www.amazon.com/Algorithms-Creative-Approach-Udi-Manber/dp/0201120372" rel="nofollow">http://www.amazon.com/Algorithms-Creative-Approach-Udi-Manbe...</a><p>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.<p>It has a good amount of proofs and a pretty strong focus on automata thought so that may not be your cup of tea.<p>Hopcroft won the Turing award in 1986 so he knows what he's talking about.
As others said: Introduction to the Theory of Computation, by Michael Sipser<p>Together with Shai Simonson's lectures:<p><a href="http://aduni.org/courses/theory/" rel="nofollow">http://aduni.org/courses/theory/</a>