Algorithms for NP-Hard Problems (Section 23.5: The Exponential Time Hypothesis)
Tim Roughgarden Lectures · 18:46
The P≠NP conjecture only says NP-hard problems need superpolynomial time, not that they need truly exponential time—subexponential bounds like \(n^{O(\log n)}\) or \(2^{O(\sqrt{n})}\) remain logically possible. The Ex...