Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



ECCC BOOKS, LECTURES AND SURVEYS > ON TEACHING THE BASICS OF COMPLEXITY THEORY:
EP07-001
Oded Goldreich

On Teaching the Basics of Complexity Theory




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.


ISSN 1433-8092 | Imprint