Introduction to Complexity Theory: Lecture Notes

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 eect 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. Specic topics included: Revisiting NP and NPC (with emphasis on search vs decision); Complexity classes dened by one resource-bound { hierarchies, gaps, etc; Non-deterministic Space complexity (with emphasis on NL); Randomized Computations (e.g., ZPP, RP and BPP).