EP07-001
Authors: Oded Goldreich
Contact: oded.goldreich"at"weizmann.ac.il



Abstract:
I would outline a conceptual framework for teaching the basic notions and results of complexity theory. The focus is on using definitions and on organizing the presentation in a way that reflects the fundamental nature of the material. I will not attempt to provide a self-contained presentation of the material itself, but rather outline my (non-innovative) suggestions regarding how this material should be presented in class. I will discuss the P-vs-NP Question, the general notion of a reduction, and the theory of NP-completeness. In particular, I 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, I suggest to highlight the mere existence of NP-complete sets.