Computer Science/Discrete Mathematics Seminar II

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.