Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?

Question

I have a simple quesiton:

It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH.

also

there is a result that says APSP can be solved in time $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ by Ryan Williams.

But, this improvement doesn't refute the conjectures.

So, what I did is as following: I compare between $\lim_{n -> \infty} \frac{( \frac{n^3}{2^{\sqrt{\log n}}})}{n^{3-\delta} } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

When I have this function: $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$, I didn't know how to compare it with other since Big Omega is only on part of it, how to compare in general with other function when you have this one?

Thanks in advance!

Answer 1

The statement "no $O(n^{3-\delta})$ algorithm exists" (for any constant $\delta>0$) means that there is no algorithm that is a polynomial factor faster than $\Theta(n^3)$. It doesn't exclude algorithms that are faster by some less than polynomial factor. For example it doesn't exclude algorithms with a running time of $\Theta(\frac{n^3}{\log n})$.

In your case, the set $2^{\Omega(\sqrt{\log n})}$ includes functions that grow slower than any polynomial. For example $2^{\sqrt{\log n}}$. To see this, pick any constant $\epsilon>0$ and notice that:

$$ \lim_{n \to \infty} \frac{2^{\sqrt{\log n}}}{n^\epsilon} = \lim_{n \to \infty} \frac{2^{\sqrt{\log n}}}{2^{\epsilon \log n}} = \lim_{n \to \infty} 2^{\sqrt{\log n} - \epsilon \log n} = 0. $$

Answer 2

It looks like the comparison in the question is wrong.

$$\begin{aligned} \lim_{n -> \infty} \frac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } &= \lim_{n -> \infty} \frac{n^{\delta} }{2^{\sqrt{\log n}}}=\lim_{n -> \infty} \frac{2^{\delta\log n} }{2^{\sqrt{\log n}}}\\ &=\lim_{n -> \infty} 2^{\delta\log n-\sqrt{\log n}}=\lim_{m -> \infty}2^{\delta m-\sqrt{m}}\\ &=\lim_{m -> \infty}2^{\sqrt m(\delta\sqrt{m} -1)}\\ &=2^{+\infty}=+\infty.\\ \end{aligned}$$

Here $\log n$ is understood as $\log_2n$. Since $\log_a n=\log_a2\cdot\log_2n$, the limit above will still be infinity if the base of $\log$ is switched to any number greater than 1.

In fact, for any constant $c>0$, however smaller it is and any constant $\delta>0$, however small it is, we still have, by similar argument,

$$\lim_{n \to \infty}\frac{\frac{n^3}{2^{c\sqrt{\log n}}}}{\ \ \ {n^{3-\delta}\ \ \ }} =+\infty.$$

---

I compare between $\lim_{n -> \infty} \frac{ \frac{n^3}{2^{\sqrt{\log n}}}}{\ \ \ n^{3-\delta}\ \ } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

To be more careful, there is another mistake in the above reasoning. Even if $\lim_{n -> \infty} \dfrac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } = 0 $, it does not imply it will refute the conjecture. The point is, "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" might be true because it can be solved in time $\frac{n^3}{2^{0.01\sqrt{\log n\ \ }}}$, not because it can be solved in time $\frac{n^3}{2^{\sqrt{\log n\ \ }}}$". If you want to use the fact that "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" to refute the conjecture, you have to show that

$$O(n^{3-\delta}) \cap \frac{n^3}{2^{\Omega(\sqrt{\log n})}} = \emptyset,$$ or, in plain words, there is no function $f\in \Omega(\sqrt{\log n})$ such that $\dfrac{n^3}f\in O(n^{3-\delta})$.

Well, in fact, the other extreme is true. $\dfrac{n^3}f\in O(n^{3-\delta})$ for all $f\in \Omega(\sqrt{\log n})$.