Introduction to Complexity Theory

Lecture Notes for a Two-Semester course [1999]

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. This course is aimed at exposing the students to the basic results and research directions in the field.

Material available on-line:

  • Preface to the lecture notes.
  • Summaries (+ links to 26 individual lecture notes).
  • The 26 individual lecture notes - see below.
  • The first 13 lecture notes (slightly revised!) in one (gzip-ed) PSfile (590K).
  • The next 13 lecture notes (slightly revised!) in one (gzip-ed) PSfile (600K).
  • All 26 lecture notes (slightly revised as above) in one file:
  • Corrections and Additions.
  • First Semester - Individual Lectures:
  • Second Semester - Individual Lectures:
  • Related Material (available on-line):
  • A brief survey on Complexity Theory (by Oded Goldreich, 2000).
  • Notes for a Single-Semester course (by Oded Goldreich, 2002).
  • Revised PowerPoint notes for some of the lectures and additional material prepared by Muli Safra.

  • Back to Oded Goldreich's homepage.

    Copyright (C symbol) 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.