Introduction to Complexity Theory

Two sets of Lecture Notes

Oded Goldreich

This website provides access to the old lecture notes that are mostly superseeded by a book (published in 2008).


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

Two sets of notes are available on-line: Additional closely related material includes

Other related material (available on-line)


Back to Oded Goldreich's homepage.