Do NP-Hard Problems Require Exponential Time?

Computer Science/Discrete Mathematics Seminar II
Topic:Do NP-Hard Problems Require Exponential Time?
Speaker:Andrew Drucker
Affiliation:Member, School of Mathematics
Date:Tuesday, April 8
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2014/0408-AndrewDrucker

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.