How to explain ETH to undergraduate students? I am a TA for complexity theory course. I want to explain the Exponential Time Hypothesis (ETH) to undergraduate students. They have done algorithm and theory of computation course. They know about SAT problem, with brute force algorithms to solve SAT. I have explained the ETH hypothesis in less than half hour.

One way is like this wikipedia


  "The hypothesis states that $3$-SAT (or any of several related NP-complete problems) cannot be solved in subexponential time in the worst case". The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It can be used to show that many computational problems are equivalent in complexity,in the sense that if one of them has a subexponential time algorithm then they all do.


I then try to explain the each important point of the of definition. I don't this will be the right way. I want to convey the significance of the ETH.

Question : How to explain ETH to undergraduate students?
It seems that you are aiming to convey the significance of disproving ETH? If you're looking to leave some impression, it's always better to show rather than tell.

I think your students need to see some examples of practical areas and difficult problems that efficiently reduce to SAT. If you can demonstrate to them that SAT is a "funnel" of sorts for many other kinds of problems, your students can piece together for themselves why solving SAT in sub-exponential time would be game-changing. 

Some example problems could include task scheduling, the traveling salesman problem (and by extension, pretty much any sort of path-finding problem), register-allocation in code compilation, general propositional logic inference, etc. You can also discuss industries that use SAT-solving already, like circuit design and e-commerce.

This would take a fair bit of work, but you could even demo using a SAT-Solver; Sudoku is a popular and relatively easy example problem, and it never fails to amaze me how quickly it solves even the hardest of puzzles. If you need one, CryptoMiniSat is a great off-the-shelf SAT-Solver https://github.com/msoos/cryptominisat/releases.