Computer Science/Discrete Mathematics Seminar II

Do NP-Hard Problems Require Exponential Time?

The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable. This idea is expressed in the influential "Exponential Time Hypothesis" (ETH) of Impagliazzo, Paturi, and Zane. In this survey talk, I will describe the ETH and its consequences (some of which are rather subtle). We will see that this hypothesis holds considerable explanatory power. I will also discuss how, for some restricted (but natural) subclasses of algorithms, an ETH-like statement can be derived from more modest hardness assumptions.

Date & Time

April 08, 2014 | 10:30am – 12:30pm

Location

S-101

Affiliation

Member, School of Mathematics