Ask HN: Good books on computational complexity?
10 comments
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.
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...
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...
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
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.
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
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/
Together with Shai Simonson's lectures:
http://aduni.org/courses/theory/
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.