<p>One such result is by <a href="http://www.sciencedirect.com/science/article/pii/0304397588901314" rel="noreferrer">Megiddo and Vishkin</a>. They proved that minimum dominating set in tournaments is in $QP$. Additionally, they showed that tournament dominating set has P-time algorithm if and only if SAT has subexponential time algorithm. Therefore, ETH falseness implies that tournament dominating set is in $P$ which seems unlikely.</p>

CC BY-SA 3.0
2017-07-02T05:52:05.243Z
2017-07-02T05:52:05.243Z
Mohammad Al-Turkistany
<p>The proof that Exponential Time Hypothesis (ETH) is true, would imply that P!=NP among other implications (like solvability of SAT in sub-exponential time is not possible in the worst case).</p>

<p>But, if proven that ETH is false, how would it impact the Complexity Hierarchy and what would be the implications of the proof. Results, that immediately follow from the ETH falseness (based on our current knowledge)?</p>

CC BY-SA 3.0
2017-06-25T08:52:28.657Z
You want hypotheses that imply ETH, such as SETH and other strong forms.  I'm not sure this is a productive way to proceed, since there seems to be significant doubt about several such strengthenings of ETH, and counterexamples to a few of the most extreme ones by Ryan Williams.  ETH seems to be close to the border of what might be true; pushing beyond that may not yield much.
András Salamon
CC BY-SA 3.0
2017-06-25T18:52:09.307Z
If I understand correctly, any stronger  than ETH (SETH and kind) hypothesis, the truth of which implies ETH would be equivalent to my query as: (1) If ETH is false, then these stronger than ETH hypothesis are false too? And since some of the proposed such hypothesis are shown to be false, we do not know about any significant impact on the Complexity Hierarchy as of date (unlike the ETH is true case) ?
TheoryQuest1
CC BY-SA 3.0
2017-06-25T18:56:57.880Z
But since ETH is false implies all NPC problems have a quasipolynomial algorithms one of implications would be $NP \subset QP$. Am I missing something? Or this is the only possible impact on Complexity Hierarchy known till date?
TheoryQuest1
CC BY-SA 3.0
2017-06-26T03:15:46.893Z
"ETH is false implies all NPC problems have a quasipolynomial algorithms": No it doesn't. Why would you think that?!
Sasho Nikolov
CC BY-SA 3.0
2017-06-26T06:32:15.813Z
my mistake (was thinking in direction of implications of ETH falseness). Its the other way around I think -
 Quasipolynomial Algorithm for an NPC would guarantee ETH is false. So, $NP \subset QP$ is a stricter condition than ETH. So, just to reiterate 'ETH is false' implication has no substantial impact on Complexity Hierarchy (based on our current knowledge) ?
TheoryQuest1
CC BY-SA 3.0
2017-07-03T00:28:49.973Z
This is obvious, but if we found a subexponential time algorithm for 3-SAT that was actually fast in practice, then this would presumably have huge implications in terms for what is practically solvable.
Noah Stephens-Davidowitz
<cc.complexity-theory>
Implication of Exponential Time Hypothesis falseness?
TheoryQuest1
# Implication of Exponential Time Hypothesis falseness?

(Asked by: username_0 on 2017-06-24)

The proof that Exponential Time Hypothesis (ETH) is true, would imply that P!=NP among other implications (like solvability of SAT in sub-exponential time is not possible in the worst case).

But, if proven that ETH is false, how would it impact the Complexity Hierarchy and what would be the implications of the proof. Results, that immediately follow from the ETH falseness (based on our current knowledge)?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: You want hypotheses that imply ETH, such as SETH and other strong forms.  I'm not sure this is a productive way to proceed, since there seems to be significant doubt about several such strengthenings of ETH, and counterexamples to a few of the most extreme ones by Ryan Williams.  ETH seems to be close to the border of what might be true; pushing beyond that may not yield much.  
> **username_0**: If I understand correctly, any stronger  than ETH (SETH and kind) hypothesis, the truth of which implies ETH would be equivalent to my query as: (1) If ETH is false, then these stronger than ETH hypothesis are false too? And since some of the proposed such hypothesis are shown to be false, we do not know about any significant impact on the Complexity Hierarchy as of date (unlike the ETH is true case) ?  
> **username_0**: But since ETH is false implies all NPC problems have a quasipolynomial algorithms one of implications would be $NP \subset QP$. Am I missing something? Or this is the only possible impact on Complexity Hierarchy known till date?  
> **username_2**: "ETH is false implies all NPC problems have a quasipolynomial algorithms": No it doesn't. Why would you think that?!  
> **username_0**: my mistake (was thinking in direction of implications of ETH falseness). Its the other way around I think -  Quasipolynomial Algorithm for an NPC would guarantee ETH is false. So, $NP \subset QP$ is a stricter condition than ETH. So, just to reiterate 'ETH is false' implication has no substantial impact on Complexity Hierarchy (based on our current knowledge) ?  
> **username_3**: This is obvious, but if we found a subexponential time algorithm for 3-SAT that was actually fast in practice, then this would presumably have huge implications in terms for what is practically solvable.  

---

## 1 answers

### Answer by username_4 on 2017-07-02. Score: 8 | Accepted answer

One such result is by [Megiddo and Vishkin](http://www.sciencedirect.com/science/article/pii/0304397588901314). They proved that minimum dominating set in tournaments is in $QP$. Additionally, they showed that tournament dominating set has P-time algorithm if and only if SAT has subexponential time algorithm. Therefore, ETH falseness implies that tournament dominating set is in $P$ which seems unlikely.


---

