TY  - BOOK
AU  - Oded Goldreich
TI  - Computational complexity: : a conceptual perspective
SN  - 9780521884730
AV  - QA267.7 
PY  - 2008///]
CY  - U.K.
PB  - Cambridge University Press
KW  - Computer Science
KW  - Computational Geometry
N1  - 1 - Introduction and Preliminaries 
2 - P, NP, and NP-Completeness 
3 - Variations on P and NP 
4 - More Resources, More Power? 
5 - Space Complexity 
6 - Randomness and Counting 
7 - The Bright Side of Hardness 
8 - Pseudorandom Generators 
9 - Probabilistic Proof Systems 
10 - Relaxing the Requirements
N2  - Complexity theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on complexity theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study. The book will also be useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers. --- summary provided by publisher
ER  -