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.



1 Answer 1


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
    Commented Apr 4, 2021 at 23:13
  • $\begingroup$ I don’t think it’s known. $\endgroup$ Commented Apr 5, 2021 at 5:13
  • $\begingroup$ "Such instances can be coded as 3SAT instances with $O(n)$ variables." Not really accurate. The number of variables for 3SAT depends on the value of $k$ from the kSAT you reduced, not on the number of clauses/variables. $\endgroup$ Commented Dec 20, 2021 at 19:06
  • $\begingroup$ The correct details can be found in the linked paper. $\endgroup$ Commented Dec 21, 2021 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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