Complexity Theory: A Modern Approach by Sanjeev Arora, Boaz Barak
Publisher: Cambridge University Press 2008
ISBN/ASIN: 0521424267
ISBN-13: 9780521424264
Number of pages: 489
This book aims to describe such recent achievements of complexity theory in the context of the classical results. It is intended to be a text and as well as a reference for self-study. This means it must simultaneously cater to many audiences, and it is carefully designed with that goal. The book will explain the context in which a certain notion is useful, and why things are defined in a certain way. Examples and solved exercises accompany key definitions. This book assumes essentially no computational background (though a slight exposure to computing may help) and very little mathematical background apart from the ability to understand proofs and some elementary probability on finite sample spaces. A typical undergraduate course on "Discrete Math" taught in many math and CS departments should suffice (together with the Appendix).
Computers & Internet Computer Science Theory of Computation Computational Complexity Theory