Class Sessions

January 14 -- Introduction and class logistics
January 16 -- Course formulation as a seminar
January 19 -- History of computational complexity
January 21 --
January 23 --
January 26 -- Mapping the universe of problems
January 28 -- Proper complexity functions and the hierarchy theorem
January 30 -- The hierarchy theorem
February 2 -- Reductions
February 4 -- Reductions
February 6 -- Problem reductions continued
February 9 -- Student presentations
February 11 -- Student presentations
February 13 -- A P-complete problem
February 16 -- Presidents Day Holiday
February 18 -- Tetris is NP-Complete (Ming)
February 20 -- Minesweeper is NP-Complete (Anthony)