Computational Complexity Theory
About this Title
Steven Rudich, Carnegie Mellon University, Pittsburgh, PA and Avi Wigderson, Institute for Advanced Study, Princeton, NJ, Editors
Publication: IAS/Park City Mathematics Series
Publication Year: 2004; Volume 10
ISBNs: 978-0-8218-2872-4 (print); 978-1-4704-3909-5 (online)
MathSciNet review: MR2090724
MSC: Primary 68Q15; Secondary 03D15, 03F20, 68-02, 68-06, 68Q17, 81P68
Computational Complexity Theory is the study of how much of a given resource is required to perform the computations that interest us the most. Four decades of fruitful research have produced a rich and subtle theory of the relationship between different resource measures and problems. At the core of the theory are some of the most alluring open problems in mathematics.
This book presents three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. The first week gives a general introduction to the field, including descriptions of the basic models, techniques, results and open problems. The second week focuses on lower bounds in concrete models. The final week looks at randomness in computation, with discussions of different notions of pseudorandomness, interactive proof systems and zero knowledge, and probabilistically checkable proofs (PCPs). It is recommended for independent study by graduate students or researchers interested in computational complexity.
The volume is recommended for independent study and is suitable for graduate students and researchers interested in computational complexity.
Graduate students and research mathematicians interested in computational complexity.
Table of Contents
Week One: Complexity theory: From Gödel to Feynman
- Complexity theory: From Gödel to Feynman
- Average case complexity
- Exploring complexity through reductions
- Quantum computation
Week Two: Lower Bounds
Week Three: Randomness in computation
- Preface to “Week Three: Randomness in Computation”
- Pseudorandomness—Part I
- Pseudorandomness—Part II
- Probabilistic proof systems—Part I
- Probabilistically checkable proofs