On Teaching the Basics of Complexity Theory

  • Oded Goldreich
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


We outline a conceptual framework for teaching the basic notions and results of complexity theory. Our focus is on using definitions and on organizing the presentation in a way that reflects the fundamental nature of the material. We do not attempt to provide a self-contained presentation of the material itself, but rather outline our suggestions regarding how this material should be presented in class. In addition, we express our opinions on numerous related issues.

We focus on the P-vs-NP Question, the general notion of a reduction, and the theory of NP-completeness. In particular, we suggest presenting the P-vs-NP Question both in terms of search problems and in terms of decision problems (where NP is viewed as a class of proof systems). As for the theory of NP-completeness, we suggest highlighting the mere existence of NP-complete sets.


Decision Problem Turing Machine Complexity Theory Proof System Search Problem 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Cook, S.A.: The Complexity of Theorem Proving Procedures. In: 3rd STOC, pp. 151–158 (1971)Google Scholar
  2. 2.
    Even, S., Selman, A.L., Yacobi, Y.: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Inform. and Control 61, 159–173 (1984)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)zbMATHGoogle Scholar
  4. 4.
    Goldreich, O.: Introduction to Complexity Theory – notes for a one-semester course. Weizmann Institute of Science, Spring (2002) Available from
  5. 5.
    Goldreich, O.: On Promise Problems: A Survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  6. 6.
    Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)Google Scholar
  7. 7.
    Ladner, R.E.: On the Structure of Polynomial Time Reducibility. Jour. of the ACM 22, 155–171 (1975)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Levin, L.A.: Universal Search Problems. Problemy Peredaci Informacii 9, 115–116 (1973); Translated in problems of Information Transmission 9, 265– 266Google Scholar
  9. 9.
    Selman, A.: On the structure of NP. Notices Amer. Math. Soc. 21(6), 310 (1974)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Oded Goldreich
    • 1
  1. 1.Department of Computer Science and Applied MathematicsWeizmann Institute of ScienceIsrael

Personalised recommendations