How to explain ETH to undergraduate students?

Question

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?

Answer 1

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.

Answer 2

I'm not sure I understand your dilemma, especially for the students you describe. Many computational problems can be shown to be "reducible" to others using a sub exponential (usually polynomial) run time algorithm. That is to say, a solution to one of these problems can be transformed into a solution of a different problem in polynomial time. The most interesting cases are those in which the transformation can be done in either direction using (say) polynomial time. Thus, if any of these equivalent problems can be solved in general in sub exponential time, then all of them can, since the transformation is sub exponential.

You can still get a doctorate for showing such equivalence of problems, in fact.

The significance is, of course, that a very large set of questions will be answered if someone can show that any of these "equivalent problems" are sub exponential and similarly if one can show that exponential time is required for any of them.

While time is the usual measure of such things, space can also be used for a similar sort of analysis. Some problems can be quickly solved using a lot of space.

I'll note that if your specific need is to show why the ETH isn't equivalent to the statement $P ≠ NP$ then I haven't said enough.