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$
  • 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$ – Huck Bennett Nov 20 '19 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. Nov 20 '19 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$ – Huck Bennett Nov 20 '19 at 16:27
  • $\begingroup$ Is this question sort of the same? cstheory.stackexchange.com/questions/9237/… $\endgroup$ – Hermann Gruber Nov 20 '19 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 Nov 22 '19 at 10:50
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).

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You mean $\alpha \in \omega (\frac{\log \log n}{\log n})$ $\endgroup$ – Saeed Mar 22 at 10:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.