<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>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 <a href="https://github.com/msoos/cryptominisat/releases" rel="nofollow noreferrer">https://github.com/msoos/cryptominisat/releases</a>.</p>

CC BY-SA 4.0
2018-12-30T20:53:40.573Z
2018-12-30T20:53:40.573Z
Matthew W.
<p>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 <em>equivalent</em> problems can be solved in general in sub exponential time, then all of them can, since the transformation is sub exponential. </p>

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

<p>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 <em>required</em> for any of them. </p>

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

<p>I'll note that if your specific need is to show why the ETH isn't <em>equivalent</em> to the statement <span class="math-container">$P ≠ NP$</span> then I haven't said enough. </p>

CC BY-SA 4.0
2018-12-30T15:50:00.647Z
2018-12-30T16:24:33.100Z
2018-12-30T16:24:33.100Z
Buffy
<p>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.</p>

<p>One way is like this <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">wikipedia</a></p>

<blockquote>
  <p>"The hypothesis states that <span class="math-container">$3$</span>-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.</p>
</blockquote>

<p>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.</p>

<p><strong>Question :</strong> How to explain ETH to undergraduate students?</p>

CC BY-SA 4.0
2018-12-30T15:51:53.847Z
I've given an answer, but I wonder if I've missed something in your question that makes it harder.
Buffy
<complexity-theory>
How to explain ETH to undergraduate students?
# How to explain ETH to undergraduate students?

(Asked by: username_0 on 2018-12-30)

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](https://en.wikipedia.org/wiki/Exponential_time_hypothesis)

> "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?

**Tags:** complexity-theory

> **Comments:**
> **username_1**: I've given an answer, but I wonder if I've missed something in your question that makes it harder.  

---

## 2 answers

### Answer by username_2 on 2018-12-30. Score: 2

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 by username_1 on 2018-12-30. Score: 1

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.


---

