Computational Complexity Theory (Ias/Park City Mathematics Series)

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. Content: Week One: Complexity theory: From Godel to Feynman Complexity theory: From Godel to Feynman History and basic concepts Resources, reductions and P vs. NP Probabilistic and quantum computation Complexity classes Space complexity and circuit complexity Oracles and the polynomial time hierarchy Circuit lower bounds "Natural" proofs of lower bounds Bibliography Average case complexity Average case complexity Bibliography Exploring complexity through reductions Introduction PCP theorem and hardness of computing approximate solutions Which problems have strongly exponential complexity? Toda's theorem: $PH\subseteq P^{\ No. P}$ Bibliography Quantum computation Introduction Bipartite quantum systems Quantum circuits and Shor's factoring algorithm Bibliography Lower bounds: Circuit and communication complexity Communication complexity Lower bounds for probabilistic communication complexity Communication complexity and circuit depth Lower bound for directed $st$-connectivity Lower bound for $FORK$ (continued) Bibliography Proof complexity An introduction to proof complexity Lower bounds in proof complexity Automatizability and interpolation The restriction method Other research and open problems Bibliography Randomness in computation Pseudorandomness Preface Computational indistinguishability Pseudorandom generators Pseudorandom functions and concluding remarks Appendix Bibliography Pseudorandomness-Part II Introduction Deterministic simulation of randomized algorithms The Nisan-Wigderson generator Analysis of the Nisan-Wigderson generator Randomness extractors Bibliography Probabilistic proof systems-Part I Interactive proofs Zero-knowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NP-hardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.

Computational complexity theory sets the formal mathematical foundations of efficient computation, asking which tasks can be performed given the limitations of computational resources. The field has expanded to include mathematical disciplines, natural and physical sciences, and social sciences such as economics. This volume came from a Park City summer program through the Institute for Advanced Study, and covers its three weeks of lectures. Topics include complexity theory (the discipline from Godel to Feynman, average case complexity, exploring complexity through reductions, and quantum computation), lower bounds (circuit and communication complexity and proof complexity) and randomness in computation (pseudo-randomness and probabilistic proof systems). Presenters include bibliographies with their groups of lectures, but this volume does not include an index. Annotation ©2004 Book News, Inc., Portland, OR

"This volume is recommended for independent study and is suitable for graduate students and researchers interested in computational complexity."--BOOK JACKET.