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.
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" :-)
you mention you want readable but then you state you want to have examples of problem & problem solving which are generally two different categories of references. here are some suggestions on readable background for general understanding and for "motivation" but not with problem sets.
a useful strategy is to look for "key/interesting/outstanding problems" in the area of study in this case complexity/computability theory. in this area the key open problem is P$\stackrel{?}{=}$NP for over 4 decades. Fortnow has released a brand new book on the subject which conveys the general significance of the problem, its deep/wideranging connections/implications, general aspects and applications of complexity theory, etc. you mention you'd like a "readable" survey and this book is very much targeted at a mass/not-overly-technical audience but also CS students should likely find it highly readable.
The golden ticket: P, NP, and the search for the impossible by Lance Fortnow. see also publisher page (Princeton university press) with TOC. see also this review by Schaefer, New York Journal of Books
Computability theory is another area that is covered in this readable ref by researcher Martin Davis: Engines of Logic: Mathematicians and the Origin of the Computer
