I know that ETH states that 3-SAT is not solvable in $2^{o(n)}$ time, the best known bound for 3-SAT is around $O(2^{.38n})$. Whereas, SETH states that there is no universal $\delta$ such that for every positive integer $k$, a $k$-SAT problem is solvable in $O(2^{\delta n})$ time.

It is not clear to me that how does SETH is stronger, and SETH implies ETH.



The more usual (and slightly stronger) formulation of the exponential time hypothesis is that there is $\epsilon > 0$ such that solving 3SAT requires time $\Omega(2^{\epsilon n})$ (see, for example, Abboud, Backurs and Williams), where $n$ is the number of variables.

The strong exponential time hypothesis states that for each $\epsilon > 0$ there exists $k\ge3$ such that solving $k$SAT requires time $\Omega(2^{(1-\epsilon)n})$ (again, see the paper mentioned above).

Showing that SETH implies ETH isn't trivial. The idea is to show that $k$SAT reduces to sparse $k$SAT, which is $k$SAT restricted to instances with $O(n)$ clauses. Such instances can be coded as 3SAT instances with $O(n)$ variables. Therefore if we can solve 3SAT in time $O(2^{\gamma n})$ for every $\gamma>0$, then we can also solve $k$SAT in time $O(2^{\gamma n})$ for every $\gamma>0$. For the details, consult Impagliazzo, Paturi and Zane, Which problems Have strongly exponential Complexity?.

  • $\begingroup$ Thanks for this answer. I know this is somewhat unrelated, but do you know what the status of the reverse implication (that is ETH implies SETH) is? $\endgroup$ – gen Apr 4 at 23:13
  • $\begingroup$ I don’t think it’s known. $\endgroup$ – Yuval Filmus Apr 5 at 5:13

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.