6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – András Salamon Jun 25 '17 at 8:52
  • 2
    $\begingroup$ 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) ? $\endgroup$ – TheoryQuest1 Jun 25 '17 at 18:52
  • 2
    $\begingroup$ 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? $\endgroup$ – TheoryQuest1 Jun 25 '17 at 18:56
  • 6
    $\begingroup$ "ETH is false implies all NPC problems have a quasipolynomial algorithms": No it doesn't. Why would you think that?! $\endgroup$ – Sasho Nikolov Jun 26 '17 at 3:15
  • 1
    $\begingroup$ 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) ? $\endgroup$ – TheoryQuest1 Jun 26 '17 at 6:32
7
$\begingroup$

One such result is by Megiddo and Vishkin. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.