Trottier Building, room 2100
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
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.