INFORMATION FOR PROSPECTIVE CSc 486 STUDENTS

Do you want to learn about one of the most important discoveries in Computer Science? Do you want to know whether a problem has a fast algorithm? Do you want to avoid working on methods that won’t be fast enough to be practical? Do you want to know precisely what it means to say that a problem is NP-hard or NP-easy? Then this is the course for you.

In the late 20^th Century, a very important discovery was made: Many natural problems, while solvable by straightforward algorithms, seem not to be solvable by any algorithm fast enough to cope with large or even medium-sized instances. It is very important to know when a problem is of this type, since knowing so enables a computer scientist to abandon looking for an algorithm that is fast and always exact, and instead look for heuristic approaches, approximations, etc. We will study this useful area.

Our textbook will be Introduction to the Theory of Computation, 2^nd edition, by Michael Sipser, a book that you may have already. We will look at complexity in general, but focus on the classes P, NP, and NPC, which are the most important in practice. We first prove the existence of NP-complete problems (the Cook-Levin Theorem), and then study how to apply the theory to the show that certain standard problems are indeed NP-complete, such as the Satisfiability, the Knapsack and the Hamilton Path problems. Finally, we will look into what to do when we need to get some sort of handle on a problem that is too difficult to yield guaranteed exact solutions.