Computational Complexity
Computational Complexity
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.
- Presents a conceptual perspective, meaning the text evolves around the underlying intuitive questions on the subject
- The focus is on motivation and ideas
- Organized around conceptual themes
Product details
No date availableAdobe eBook Reader
9780511402685
0 pages
0kg
Table of Contents
- 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
- Epilogue
- Appendix A. Glossary of complexity classes
- Appendix B. On the quest for lower bounds
- Appendix C. On the foundations of modern cryptography
- Appendix D. Probabilistic preliminaries and advanced topics in randomization
- Appendix E. Explicit constructions
- Appendix F. Some omitted proofs
- Appendix G. Some computational problems.
