[Solved]: Introduction to complexity and computability

ignougroup
Problem Detail: 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