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

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
NPcompleteness and NPhardness 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.