1
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
1
  • 2
    $\begingroup$ You mean $\alpha \in \omega (\frac{\log \log n}{\log n})$ $\endgroup$
    – Saeed
    Commented Mar 22, 2020 at 10:20

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.