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.