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.

brief survey

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:

in gzip-ed PostScript (PS) format (1040K).
in gzip-ed DVI format (some figures missing!) (600K).
in PDF format with a clickable Table of Contents (converted by D.W. Barnes).

Corrections and Additions.

First Semester - Individual Lectures:

Lecture 1: P vs NP.
Lecture 2: NP-completeness.
Lecture 3: More on NP and some on DTIME.
Lecture 4: Space complexity.
Lecture 5: Non-Deterministic Space.
Lecture 6: The structure of NL.
Lecture 7: Randomized Computation.
Lecture 8: Non-Uniform Polynomial-Time (P/poly).
Lecture 9: The Polynomial-Time Hierarchy.
Lecture 10: #P and Approximating it.
Lecture 11: Interactive Proofs.
Lecture 12: Probabilistically Checkable Proofs (PCP).
Lecture 13: Pseudorandom Generators.

Second Semester - Individual Lectures:

Lecture 14: Constructing Pseudorandom Generators.
Lecture 15: Derandomizing BPP (The NW-generator).
Lecture 16: Pseudorandomness in space-bounded computation.
Lecture 17: Zero-Knowledge Proofs.
Lecture 18: NP in PCP[poly,O(1)]
Lecture 19: Dtime(t) in Dspace(t/log t).
Lecture 20: NC, AC, and CircuitDepth vs Machine Space.
Lecture 21: Communication Complexity.
Lecture 22: Circuit Depth and Communication Complexity.
Lecture 23: Communication Complexity (The FORK Game).
Lecture 24: Average-Case Complexity.
Lecture 25: Computational Learning Theory.
Lecture 26: Relativization.

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.