### Research Experience for Undergraduates (REU) Seminar

Title: How fast can NP-Complete problems be solved in worst case?

Speaker: **Michael Saks**, Rutgers University

Date: June 29, 2004 1 - 2 pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

It is widely believed that any algorithm that solves an NP-Complete
problem must have running time that, in worst case, is an exponential
function of the size of the input. Researchers have developed ad hoc
algorithms for specific problems that work surprisingly well in practice.
These algorithms tend to be rather complicated and it is difficult to
prove anything about their worst case behavior.

In this talk, I'll discuss the problem of developing algorithms
for NP-complete problems whose PROVABLE worst case running time is as
small as possible. I'll concentrate on three computational problems:
(1) hamiltonian cycle, (2) chromatic number, and (3) Boolean CNF
satisfiability.