<p>If <span class="math-container">$\alpha \in O\left(\frac{\log\log n}{ \log n}\right)$</span>, then you would have proved that <span class="math-container">$P = NP$</span>, since <span class="math-container">$n^{\alpha} \in O(\log n)$</span> and <span class="math-container">$2^{n^{\alpha}} \in O(\mathrm{poly}(n))$</span>. </p>

<p>On the other hand, for <span class="math-container">$\alpha \in \omega\left(\frac{\log\log n}{ \log n}\right)$</span> and <span class="math-container">$\alpha \in o(1)$</span>, I think the most interesting thing that happens is breaking <strong>ETH</strong> with all its consequences (including breaking <strong>SETH</strong> and many other conditional lower-bounds on polynomial and parameterized problems). </p>

CC BY-SA 4.0
2020-03-22T10:20:09.463Z
You mean $\alpha \in \omega (\frac{\log \log n}{\log n})$
Saeed
CC BY-SA 4.0
2019-11-23T13:26:34.700Z
2020-03-22T14:29:15.097Z
2020-03-22T14:29:15.097Z
Narek Bojikian
<p>If we have a <span class="math-container">$2^{n^a}$</span> algorithm to <span class="math-container">$K$</span>-<span class="math-container">$SAT$</span> where <span class="math-container">$a&lt;1$</span> for all <span class="math-container">$K&gt;2$</span> then <span class="math-container">$ETH$</span> fails and literature gives consequences. What are the consequences if <span class="math-container">$a=o(1)$</span>?</p>

CC BY-SA 4.0
2019-11-20T16:02:15.320Z
The title and question don't match. The assertion that there is no $2^{n^a}$-time algorithm for $k$-SAT with $a = o(1)$ is a weaker statement than ETH.
Huck Bennett
CC BY-SA 4.0
2019-11-20T16:15:44.943Z
$2^{n^{1/\log\log n}}$ falls under $2^{n^{o(1)}}$ while $2^{n^{0.99999}}$ falls under $2^{n^a}$ with $a<1$.
VS.
CC BY-SA 4.0
2019-11-20T16:27:07.097Z
Yes, and $2^{n^{1/\log \log n}} = o(2^{n^{0.9999}})$, so asserting that there is no $2^{n^{1/\log \log n}}$-time algorithm for $k$-SAT is weaker than asserting that there is no $2^{n^{0.9999}}$-time algorithm.
Huck Bennett
CC BY-SA 4.0
2019-11-20T20:27:48.050Z
Is this question sort of the same? https://cstheory.stackexchange.com/questions/9237/consequences-of-sub-exponential-proofs-algorithms-for-sat
Hermann Gruber
CC BY-SA 4.0
2019-11-22T10:50:23.070Z
ETH is related to 3-SAT, but not for k-SAT [the SETH is related to k-SAT with different definition than ETH]
YOUSEFY
CC BY-SA 4.0
2019-11-23T13:18:40.490Z
@YOUSEFY both conjectures are very related through the sparsification lemma. SETH implies ETH
Narek Bojikian
<ds.algorithms><sat>
Potentially stronger form of non-$ETH$
VS.
# Potentially stronger form of non-$ETH$

(Asked by: username_0 on 2019-11-20)

If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?

**Tags:** ds.algorithms, sat
> **Comments:**
> **username_1**: The title and question don't match. The assertion that there is no $2^{n^a}$-time algorithm for $k$-SAT with $a = o(1)$ is a weaker statement than ETH.  
> **username_0**: $2^{n^{1/\log\log n}}$ falls under $2^{n^{o(1)}}$ while $2^{n^{0.99999}}$ falls under $2^{n^a}$ with $a<1$.  
> **username_1**: Yes, and $2^{n^{1/\log \log n}} = o(2^{n^{0.9999}})$, so asserting that there is no $2^{n^{1/\log \log n}}$-time algorithm for $k$-SAT is weaker than asserting that there is no $2^{n^{0.9999}}$-time algorithm.  
> **username_2**: Is this question sort of the same? https://cstheory.stackexchange.com/questions/9237/consequences-of-sub-exponential-proofs-algorithms-for-sat  
> **username_3**: ETH is related to 3-SAT, but not for k-SAT [the SETH is related to k-SAT with different definition than ETH]  
> **username_4**: @YOUSEFY both conjectures are very related through the sparsification lemma. SETH implies ETH  

---

## 1 answers

### Answer by username_4 on 2019-11-23. Score: 4

If $\alpha \in O\left(\frac{\log\log n}{ \log n}\right)$, then you would have proved that $P = NP$, since $n^{\alpha} \in O(\log n)$ and $2^{n^{\alpha}} \in O(\mathrm{poly}(n))$.

On the other hand, for $\alpha \in \omega\left(\frac{\log\log n}{ \log n}\right)$ and $\alpha \in o(1)$, I think the most interesting thing that happens is breaking **ETH** with all its consequences (including breaking **SETH** and many other conditional lower-bounds on polynomial and parameterized problems).

> **Comments:**
> **username_5**: You mean $\alpha \in \omega (\frac{\log \log n}{\log n})$  

---

