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):**

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.