COMP 506
Introduction to Complexity Theory

Prerequisite: a C or higher in COMP 330 or COMP 360 or COMP 362

Winter 2007-08
TuTh 1:05-2:25pm
Trottier Building, room 2100
Prof. Whitesides


The first meeting is Thursday, January 3, 2008.

One goal of computer science is to design fast algorithms to solve basic problems. However many problems, including ones of great practical importance, apparently do not admit fast algorithmic solutions. Therefore the problems themselves become an important object of study. The ability to determine that a problem is unlikely to admit a reasonably fast solution is invaluable for algorithm designers; the theory of such problems is a basic subject in its own right.

In this course, we seek methods for comparing the relative difficulty of problems, for determining which problems are unlikely to admit fast solution, and which problems are unlikely to admit even reasonable approximate solution. We also study methods for dealing with difficult problems, such as providing fast approximate solutions (when they exist) or identifying subproblems that can be solved efficiently.

Students should come away from the course with good facility at reading and understanding NP-completeness and NP-hardness proofs and some skill at inventing their own proofs, plus some knowledge of methods for dealing with intractable problems and current research themes in the area.