# Potentially stronger form of non-$ETH$

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)$$?

• 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. Nov 20, 2019 at 16:02
• $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.
Nov 20, 2019 at 16:15
• 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. Nov 20, 2019 at 16:27
• Is this question sort of the same? cstheory.stackexchange.com/questions/9237/… Nov 20, 2019 at 20:27
• ETH is related to 3-SAT, but not for k-SAT [the SETH is related to k-SAT with different definition than ETH] Nov 22, 2019 at 10:50

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).
• You mean $\alpha \in \omega (\frac{\log \log n}{\log n})$ Mar 22, 2020 at 10:20