Exponential Time Hypothesis (ETH) says that there is a real number $s=s_3>0$ such that 3-SAT with $n$ variables and $m$ clauses cannot be solved in $2^{sn}(n+m)^{O(1)}$ time. The corollary "3-SAT cannot be solved in $2^{o(n)}(n+m)^{O(1)}$ time" is used more often.

Assuming ETH is true, is anything proved about how large $s$ is?
If not, is there at least a general consensus?

  • 5
    $\begingroup$ Even if you allow to use the SETH, I am not aware of any consequences on the value of $s_3$. $\endgroup$ Mar 18 '21 at 10:32
  • $\begingroup$ If possible, I would like not to bring in stronger assumptions like SETH $\endgroup$ Mar 18 '21 at 10:52
  • 6
    $\begingroup$ I don't understand the comment. The SETH is a stronger assumption than the ETH. If we are not aware of any concrete bounds on $s_3$ when assuming the SETH, then there should be, in particular, no known bounds when assuming the ETH. $\endgroup$ Mar 18 '21 at 11:10
  • 3
    $\begingroup$ Related: people.csail.mit.edu/rrw/On_Super_Strong_ETH.pdf. I think a result of the form "if 3-SAT takes $2^{\Omega(n)}$ time then it must take $2^{0.0349n}$ time" would be very surprising. $\endgroup$ Mar 18 '21 at 17:37

Your Answer

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

Browse other questions tagged or ask your own question.