Introduction to Complexity Theory

Notes for a Single-Semester course [2002]

Oded Goldreich

This website provides access to the old lecture notes that are superseeded by a recent book.

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.

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.

Fetch: the notes in one PostScript file. Individual files are available for:

Related Material (available on-line):

  • A brief survey on Complexity Theory (by Oded Goldreich, 2000).
  • Lecture notes for a two-semester course

  • Back to Oded Goldreich's homepage.

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