Complexity Theory - On teaching its basics

(In Memory of Shimon Even [1935--2004])

Oded Goldreich


Material available on-line: 1st version, February 2005. [Revisions: July 2005, Aug. 2005] [in PDF].

We outline a conceptual framework for teaching the basic notions and results of complexity theory. Our focus is on using definitions (e.g., of NP) and on organizing the presentation (e.g., of NP-completeness) 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 (non-innovative) suggestions regarding how this material should be presented in class.

We discuss the P-vs-NP Question, the general notion of a reduction, and the theory of NP-completeness. In particular, we suggest to present 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 to highlight the mere existence of NP-complete sets.

Related material: P, NP, and NP-completeness (draft for a textbook).
See also various exponsitions related to complexity theory and class notes for introduction to complexity theory.


Back to Oded Goldreich's homepage.


Copyright (C symbol) 2005 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.