Dexter C Kozen

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.

Amazon.com info
Hardcover 418 pages  
ISBN: 1846282977
Salesrank: 2213736
Weight:1.98 lbs
Published: 2006 Springer
Amazon price $89.17
Marketplace:New from $81.26:Used from $61.00
Buy from Amazon.com
Amazon.co.uk info
Hardcover 418 pages  
ISBN: 1846282977
Salesrank: 193252
Weight:1.98 lbs
Published: 2006 Springer
Amazon price £72.00
Marketplace:New from £71.13:Used from £51.08
Buy from Amazon.co.uk
Amazon.ca info
Hardcover 418 pages  
ISBN: 1846282977
Salesrank: 1318778
Weight:1.98 lbs
Published: 2006 Springer
Amazon price CDN$ 128.24
Marketplace:New from CDN$ 128.24:Used from CDN$ 80.60
Buy from Amazon.ca





Product Description

This textbook is uniquely written with dual purpose. It cover cores material in the foundations of computing for graduate students in computer science and also provides an introduction to some more advanced topics for those intending further study in the area. This innovative text focuses primarily on computational complexity theory: the classification of computational problems in terms of their inherent complexity. The book contains an invaluable collection of lectures for first-year graduates on the theory of computation. Topics and features include more than 40 lectures for first year graduate students, and a dozen homework sets and exercises.