| The theory of NP-completeness is studies: complexity, the problem classes P and NP, intractability, Cook’s theorem. The student will learn how to recognize if a problem is NP-complete or NP-hard and how to solve these hard problems using approximation algorithms. A short introduction to complexity theory is given. Although many famous problems are studies (traveling salesman, graph coloring, knapsack), the emphasis is on the general techniques. Prerequisite: CS 3933 or consent of instructor. |
