5
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you Steven! it is very clear! well done! $\endgroup$ – user777 Apr 25 '20 at 15:35
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you John, your answer is also amazing. It is equal 0 because $2^{\sqrt{\log n}}*n^{3-\delta}=\sqrt{2}n^{4-\delta}$. Thus, denominator would be bigger than $n^{3}$, thus as n approaches to infinity, the limit goes to zero. $\endgroup$ – user777 Apr 25 '20 at 19:21
  • $\begingroup$ But, if I say for $\delta >1$, in my argument, then numerator is greater and therefore goes to infinity. $\endgroup$ – user777 Apr 25 '20 at 19:28
  • 1
    $\begingroup$ $2^{\sqrt{\log n}}*n^{3-\delta}=\sqrt{2}n^{4-\delta}$ is not correct. Try $n=100000000.0, \delta=0.5$ or $n=100000000.0, \delta=1.5$ in Python or your favorite programing language or a calculator. $\endgroup$ – John L. Apr 26 '20 at 2:36
  • 1
    $\begingroup$ You're correct, it is not correct, in fact, this is a mistake where $2^{\log^{1/2}n}$ is not the same as $2^{\log n^{1/2}}$. I considered the second one in my analysis which is wrong. Thank you again John! $\endgroup$ – user777 Apr 26 '20 at 4:40

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.