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.
(
9 comments
| 16 points
| on HN
)
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.
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...
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...
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
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.
Great material, great exercises, very good bibliography
Together with Shai Simonson's lectures:
http://aduni.org/courses/theory/