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


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.