Instructor: Ron Prather
Webpage: http://www.cs.trinity.edu/~rprather
Email: rprather@brandxnet.com
Text: M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
This course is a survey of the theory of computational complexity, with special emphasis on the notion of NP-completeness. The course begins with an introduction to computational problems, algorithms, and their complexity. Various models of computation, particularly deterministic and nondeterministic Turing machines, are reviewed.
The following chapters of the text are given particular emphasis:
The central focus of the course is that of the distinction between tractable (polynomial-time) and intractable problems, thus leading to the concepts of polynomial reducibility and NP-completeness, together with their related complexity classes P, NP and NP-complete. Deriving from Cook's Theorem, a number of important classical problems in mathematics and computer science are shown to be NP-complete. These examples form the heart of the course. Time permitting, additional complexity classes, e.g., P-space, are discussed, and various approximation algorithms for NP-complete problems are studied.
Students are expected to be able to understand and to create for themselves convincing proofs of complexity and NP-completeness results. Both written and oral communication of such proofs is a fundamental requirement. (On occasion, students will be asked to present such results at the blackboard to the class.)
Grading: The course grade will be computed as follows:
The format for the exams, e.g., whether open or closed book, will be announced one week in advance.
Late homework is to be discouraged and may not be accepted. All such work must represent individual effort. If there is substantial use of outside sources, such references must be cited.