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