On Teaching the Basics of Complexity Theory
- 751 Downloads
We outline a conceptual framework for teaching the basic notions and results of complexity theory. Our focus is on using definitions and on organizing the presentation 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 suggestions regarding how this material should be presented in class. In addition, we express our opinions on numerous related issues.
We focus on the P-vs-NP Question, the general notion of a reduction, and the theory of NP-completeness. In particular, we suggest presenting 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 highlighting the mere existence of NP-complete sets.
KeywordsDecision Problem Turing Machine Complexity Theory Proof System Search Problem
Unable to display preview. Download preview PDF.
- 1.Cook, S.A.: The Complexity of Theorem Proving Procedures. In: 3rd STOC, pp. 151–158 (1971)Google Scholar
- 4.Goldreich, O.: Introduction to Complexity Theory – notes for a one-semester course. Weizmann Institute of Science, Spring (2002) Available from http://www.wisdom.weizmann.ac.il/~oded/cc.html
- 6.Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)Google Scholar
- 8.Levin, L.A.: Universal Search Problems. Problemy Peredaci Informacii 9, 115–116 (1973); Translated in problems of Information Transmission 9, 265– 266Google Scholar
- 9.Selman, A.: On the structure of NP. Notices Amer. Math. Soc. 21(6), 310 (1974)Google Scholar