<p>Exponential Time Hypothesis (ETH) says that there is a real number <span class="math-container">$s=s_3&gt;0$</span> such that 3-SAT with <span class="math-container">$n$</span> variables and <span class="math-container">$m$</span> clauses cannot be solved in <span class="math-container">$2^{sn}(n+m)^{O(1)}$</span> time. The corollary &quot;3-SAT cannot be solved in <span class="math-container">$2^{o(n)}(n+m)^{O(1)}$</span> time&quot; is used more often.</p>
<p><strong>Assuming ETH is true, is anything proved about how large <span class="math-container">$s$</span> is?</strong><br />
If not, is there at least a general consensus?</p>

CC BY-SA 4.0
2021-03-18T10:32:29.837Z
Even if you allow to use the SETH, I am not aware of any consequences on the value of $s_3$.
Christian Komusiewicz
CC BY-SA 4.0
2021-03-18T10:52:38.900Z
If possible, I would like not to bring in stronger assumptions like SETH
Cyriac Antony
CC BY-SA 4.0
2021-03-18T11:10:47.890Z
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.
Christian Komusiewicz
CC BY-SA 4.0
2021-03-18T17:37:32.347Z
Related: https://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.
Huck Bennett
<complexity-assumptions>
Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)
Cyriac Antony
# Size of the constant $s_3$ in Exponential Time Hypothesis (ETH)

(Asked by: username_0 on 2021-03-18)

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?

**Tags:** complexity-assumptions
> **Comments:**
> **username_1**: Even if you allow to use the SETH, I am not aware of any consequences on the value of $s_3$.  
> **username_0**: If possible, I would like not to bring in stronger assumptions like SETH  
> **username_1**: 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.  
> **username_2**: Related: https://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.  

---

## 0 answers

