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:
- Preface and Table of Contents
- Part I: Things that should have been
taught in previous courses
- Lecture 1: P versus NP
- Lecture 2: Reductions and Self-reducibility
- Lecture 3: NP-completeness
- Historical Notes for the first series
- Part II: The most traditional material
- Lecture 4: Complexity classes defined by a sharp threshold
- Lecture 5: Space Complexity
- Lecture 6: The Polynomial-Time Hierarchy
- Lecture 7: Randomized Complexity Classes
- Lecture 8: Non-Uniform Complexity
- Lecture 9: Counting Classes
- Lecture 10: Space is more valuable than time [not included]
- Lecture 11: Circuit Depth and Space Complexity [not included]
- Historical Notes for the second series
- Part III: The less traditional material
- Lecture 12: Probabilistic Proof Systems
- Lecture 13: Pseudorandomness
- Lecture 14: Average-Case Complexity
- Lecture 15: Circuit Lower Bounds [not included]
- Lecture 16: Communication Complexity [not included]
- Historical Notes for the second series
- Bibliography
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.