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.
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.
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.