Introduction to Complexity Theory { Lecture Notes Oded Goldreich Department of Computer Science and Applied Mathematics Weizmann Institute of Science, Israel. Email:
[email protected] July 31, 1999
I
c Copyright 1999 by Oded Goldreich.
Permission to make copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that new copies bear this notice and the full citation on the rst page. Abstracting with credit is permitted.
II
Preface Complexity Theory is a central eld of Theoretical Computer Science, with a remarkable list of celebrated achievements as well as a very vibrant present research activity. The eld is concerned with the study of the intrinsic complexity of computational tasks, and this study tend to aim at generality: It focuses on natural computational resources, and the e ect of limiting those on the class of problems that can be solved. These lecture notes were taken by students attending my year-long introductory course on Complexity Theory, given in 1998{99 at the Weizmann Institute of Science. The course was aimed at exposing the students to the basic results and research directions in the eld. The focus was on concepts and ideas, and complex technical proofs were avoided. Speci c topics included: Revisiting NP and NPC (with emphasis on search vs decision); Complexity classes de ned by one resource-bound { hierarchies, gaps, etc; Non-deterministic Space complexity (with emphasis on NL); Randomized Computations (e.g., ZPP, RP and BPP); Non-uniform complexity (e.g., P/poly, and lower bounds on restricted circuit classes); The Polynomial-time Hierarchy; The counting class #P, ap