A conceptual introduction to modern topics in complexity for advanced undergraduate and graduate students.
Inhaltsverzeichnis
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.
