Theory of computation

When I started Theory of computation by Dexter C. Kozen I had the feeling of being thrown in at the deep end. This is not the sort of book with a gentle introduction to the subject of computational complexity. Rather it is aimed at the postgraduate level, and so assumes that the student will have previous experience of the subject. That said, it seems remarkably self contained, with at least a sketch of the important proofs of the subject. It also has an extensive set of exercises for each chapter with solutions, and so would be an excellent choice for independent students, provided they have sufficient background knowledge of the subject.

The book consists of short chapters, each based on a lecture the author has given. Kozen is thus able to pack a lot into the 270 pages of the main book. The book deals well with notions such as Alternating Turing Machines and Oracles, which are only sketched upon elsewhere, and so gives the reader a good background on how to prove time and space lower bounds for computational problems. There are also supplementary lectures on subjects such as transfinite ordinals and how they fit into the theory of computational complexity. In conclusion I would say that if you're hoping to prove that P≠NP then this book will help to provide the level of knowledge of the subject that you will need.