Computational Complexity A Conceptual Perspective [Hardcover]

A conceptual introduction to modern topics in complexity for advanced undergraduate and graduate students.This book offers a conceptual introduction to the study of the intrinsic complexity of computational tasks. It is intended to serve advanced undergraduate and graduate students, either as a textbook or for self-study. It is also useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness, and probabilistic proof systems.This book offers a conceptual introduction to the study of the intrinsic complexity of computational tasks. It is intended to serve advanced undergraduate and graduate students, either as a textbook or for self-study. It is also useful to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness, and probabilistic proof systems.This book offers a comprehensive perspective to modern topics in complexity theory, which is a central field of the theoretical foundations of computer science. It addresses the looming question of what can be achieved within a limited amount of time with or without other limited natural computational resources. Can be used as an introduction for advanced undergraduate and graduate students as either a textbook or for self-study, or to experts, since it provides expositions of the various sub-areas of complexity theory such as hardness amplification, pseudorandomness and probabilistic proof systems.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. ProbabilistlÓU