Introduction to Complexity Theory

(Lecture Notes - Preface)

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.

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;

It was assumed that students have taken a course in computability, and hence are familiar with Turing Machines.

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.

State of these notes

These notes are neither complete nor fully proofread, let alone being far from uniformly well-written (although the notes of some lectures are quite good). Still, I do believe that these notes suggest a good outline for an introduction to complexity theory course.

Using these notes

A total of 26 lectures were given, 13 in each semester. In general, the pace was rather slow, as most students were first year graduates and their background was quite mixed. In case the student body is uniformly more advanced one should be able to cover much more in one semester. Some concrete comments for the teacher follow

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.

Bibliographic Notes

There are several books which cover small parts of the material. These include:

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.

However, the presentation of material in these lecture notes does not necessarily follow these sources.

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

Acknowledgments

I am most grateful to the students who have attended the course and partipiated in the project of preparing the lecture notes. So thanks to Sergey Benditkis, Reshef Eilon, Michael Elkin, Amiel Ferman, Dana Fisman, Danny Harnik, Tzvika Hartman, Tal Hassner, Hillel Kugler, Oded Lachish, Moshe Lewenstein, Yehuda Lindell, Yoad Lustig, Ronen Mizrahi, Leia Passoni, Guy Peer, Nir Piterman, Ely Porate, Yoav Rodeh, Alon Rosen, Vered Rosen, Noam Sadot, Il'ya Safro, Tamar Seeman, Ekaterina Sedletsky, Reuben Sumner, Yael Tauman, Boris Temkin, Erez Waisbard, and Gera Weiss.

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.