Introduction to Complexity Theory
Two sets of Lecture Notes
Oded Goldreich
Complexity Theory is a central field of Theoretical Computer Science, with a remarkable list of celebrated achievements as well as a very vibrant present research activity. The field 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 effect of limiting those on the class of problems that can be solved. The course is aimed at exposing the students to the basic results and research directions in the field.
MATERIAL AVAILABLE ON-LINE
- Lecture notes for a Two-Semester introductory course (1999). These notes are quite detailed. They were written by graduate students attending a two-semester given at the Weizmann Institute in 1998-99.
Copyright © 1999 by Oded Goldreich. Permission to make digital or hard 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 profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.
This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.
- Notes for a Single-Semester course (2002). These notes were written by Oded Goldreich and are less detailed. These notes provide an outline of an introductory course on complexity theory, including discussions and sketches of the various notions, definitions and proofs. The latter are presented in varying level of detail, where the level of detail does not reflect anything (except the amount of time spent in writing). The partition of the material to lectures only reflects the logical organization of the material, and does not reflect the amount of time to be spent on each topic. Indeed, some lectures are much longer than other. Lastly, be warned that the notes are neither complete nor fully proofread.
Related Material (available on-line)
