Topic for Spring 2001: Complexity Theory.
Finding the greatest common divisor of two integers is easier than finding a minimum weight spanning tree. This is, in turn, easier than inverting a matrix which is easier than deciding if two graphs are isomorphic. This may or may not be easier than factoring a large integer. There are thousands of problems that are just as hard as coloring a graph. It may be harder to get an approximate coloring than an approximate answer to almost any other of these equivalent problems. Nobody knows whether graph coloring is really hard but that is what almost everybody suspects. This course will survey some highlights of the complexity classes P and NP and investigate NP-completeness at some depth (think of distinguishing between easy problems and probably hard problems).
Topics from recent years: