I'm looking for a good book that explains these subjects in a readable way. Any suggestions ?
I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr theory of computation and complexity. I would like to have more reference and sources of knowledge so I can understand the subject better. Examples and solutions for various problems like proving undecidability, many to one reductions, etc can help me alot.
Asked By : Mellowcandle
Answered By : Vor
For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"):
1) Introduction to the Theory of Computation by Michael Sipser
It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references.
2) Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey
The "bible" of NP-completeness. Although the second part is a mere list of NP-complete problems (with hints on the reductions), the first part is a good introduction to computational complexity and is focused on the theory of NP-completeness (but there are no exercises).
3) Computational Complexity: A Modern Approach by Sanjeev Arora
... This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation.... It has plenty of examples/exercises (unfortunately some nice (advanced) topics like Kolmogorov complexity or Descriptive complexity are missing).
Finally, if you need more intermediate/advanced books on computational complexity, then take a look to
Lance Fortnow's Favorite Computational Complexity books list on Amazon ...
without any doubt a bunch of "gems" :-)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11399
0 comments:
Post a Comment
Let us know your responses and feedback