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.

These lecture notes were taken by students attending my year-long introductory course on Complexity Theory, given in 1998-99 at the Weizmann Institute of Science. The course was aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts and ideas, and complex technical proofs were avoided. Specific topics included:

- Revisiting NP and NPC (with emphasis on search vs decision);
- Complexity classes defined by one resource-bound - hierarchies, gaps, etc;
- Non-deterministic Space complexity (with emphasis on NL);
- Randomized Computations (e.g., ZPP, RP and BPP);
- Non-uniform complexity (e.g., P/poly, and lower bounds on restricted circuit classes);
- The Polynomial-time Hierarchy;
- The counting class #P, approximate-#P and uniqueSAT;
- Probabilistic proof systems (i.e., IP, PCP and ZK);
- Pseudorandomness (generators and derandomization);
- Time versus Space (in Turing Machines);
- Circuit-depth versus TM-space (e.g., AC, NC, SC);
- Average-case complexity;

Most of the presented material is quite independent of the specific (reasonable) model of computation, but some (e.g., Lectures 5, 16, and 19-20) depends heavily on the locality of computation of Turing machines.

- Lectures 1 and 2 revisit the P vs NP question and NP-completeness. The emphasis is on presenting NP in terms of search problems (rather than in terms of non-deterministic machines), on the fact that the mere existence of NP-complete sets is interesting (and easily demonstratable), and on reductions applicable also in the domain of search problems (i.e., Levin reductions). A good undergraduate computability course should cover this material, but unfortunately this is often not the case. Thus, I suggest to give Lectures 1 and 2 if and only if the previous courses taken by the students failed to cover this material.
- There is something anal in much of Lectures 3 and 5. One may prefer to shortly discuss the material of these lectures (without providing proofs) rather than spend 4 hours on them. (Note that many statements in the course are given without proof, so this will not be an exception.)
- One should be able to merge Lectures 13 and 14 into a single lecture (or at most a lecture and a half). I failed to do so due to inessential reasons. Alternatively, one may merge Lectures 13-15 into two lectures.
- Lectures 21-23 were devoted to communication complexity and circuit depth lower bounds derived via communication complexity. Unfortunately, this sample fails to touch upon other important directions in circuit complexity (e.g., size lower bound for AC0 circuits). I would recommend to try to correct this deficiency.
- Lecture 25 was devoted to Computational Learning Theory. This area, traditionally associated with ``algorithms'', does have a clear ``complexity'' flavour.
- Lecture 26 was spent discussing the (limited in our opinion) meaningfulness of relativization results. The dilemma of whether to discuss something negative or just ignore it is never easy.
- Many interesting results were not covered. In many cases this is due to the trade-off between their conceptual importance as weighted against their technical difficulty.

- Garey, M.R., and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
- O. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics series (Vol. 17), Springer, 1998. Copies have been placed in the faculty's library.
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
- M. Sipser. Introduction to the Theory of Computation, PWS Publishing Company, 1997.

Each lecture is planned to include bibliographic notes, but this intension has been only partially fulfilled so far.

I am grateful to Ran Raz and Dana Ron who gave guest lectures during the course: Ran gave Lectures 21-23 (on communication complexity and circuit complexity), and Dana gave Lecture 25 (on computational learning theory).

Thanks also to Paul Beame, Ruediger Reischuk and Avi Wigderson who have answered some questions I've had while preparing this course.

Brief summaries of individual lectures (in HTML form).

Back to Oded Goldreich's homepage or to main page of these notes.

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.