为什么$ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）} $不反驳下限$ o（n ^ {3- \ delta}）$？

Question

我有一个简单的quesiton：

猜测，所有对最短路径（APSP）都没有 $ o（n ^ {3- \ delta）} $ -time算法，适用于任何 $ \ delta> 0 $ by seth。

也

结果表明，APSP可以及时解决 $ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ by ryan williams

但是，这种改进不反驳猜想。

所以，我所做的是如下：我比较 $ \ lim_ {n - > \ idty} \ frac {（\ frac {n ^ 3} {2 ^ { \ SQRT {\ n登录}}}）} {N ^ {3- \增量}}= 0 $ 因此，<跨度类= “数学容器”> $ \压裂{N ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ 比另一个更好，为什么它并不意味着我们反驳猜想。

当我有这个函数时： $ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）} $ ，自从大欧米加只在一部分，我不知道如何将其与其他人进行比较，如何在您拥有此一个功能时与其他功能进行比较？

提前感谢！

Answer 1

语句“no $ o（n ^ {3- \ delta}）$ 算法存在”（对于任何常量 $ \ delta> 0 $ ）意味着没有算法是多项式因子更快，而不是 $ \ theta（n ^ 3） $ 。它不会排除算法，这些算法比多项式因子更快。例如，它不会排除具有 $ \ theta（\ frac {n ^ 3} {\ log n}）$ 的运行时间的算法。

在您的情况下，set $ 2 ^ {\ oomega（\ sqrt {\ log n}）} $ 包含比任何多项式更慢的函数。例如 $ 2 ^ {\ sqrt {\ log n}} $ 。要查看此，请选择任何常量 $ \ epsilon> 0 $ 并注意：

$$ \ lim_ {N \到\ infty} \压裂{2 ^ {\ SQRT {\ n登录}}} {N ^ \小量}= \ lim_ {N \到\ infty} \压裂{2 ^ {\ SQRT {\ LOG N}}} {2 ^ {\小量\日志N}}= \ lim_ {n \ to \ idty} 2 ^ {\ sqrt {\ log n} - \ epsilon \ log n}= 0。 $$

Answer 2

看起来问题的比较是错误的。

$$ \ begin {seconald} \ lim_ {N - > \ infty} \压裂{\压裂{N ^ 3} {2 ^ {\ SQRT {\日志N}}}} {\ \n^ {3- \增量} \ \}＆=lim_ {n - > \ infty} \ frac {n ^ {\ delta}} {2 ^ {\ sqrt {\ lum_ {n - > \ idty} \ 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。\\ \结束{对齐} $$

此处 $ \ log n $ 被理解为 $ \ log_2n $ 。由于<跨越类=“math-container”> $ \ log_a n=log_a2 \ cdot \ log_2n $ ，因此，如果 $的基础，则上述限制仍然是无穷大的\ log $ 切换到大于1的任何数字。

事实上，对于任何常量 $ c> 0 $ ，但它是较小的，它是任何常量 $ \ delta> 0 $ ，但是，它仍然是，通过类似的参数，

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

---

我比较 $ \ lim_ {n - > \ idty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}}} {\ \ \n^ {3- \ delta} \ \}= 0 $ so， $ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ 比另一个更好，为什么它并不意味着我们反驳猜想。

更加小心，在上述推理中还有另一个错误。即使 $ \ lim_ {n - > \ idty} \ dfrac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}}}}}}}}}}}}}}}}}}}}}}} {2 ^ {3- \ delta} \ \}= 0 $ ，它并不意味着它将反驳猜想。关键是，“apsp可以在时间中解决 $ \ dfrac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n \}）} $ “可能是真的，因为它可以在时间 $ \ frac {n ^ 3} {2 ^ {0.01 \ sqrt {\ log n \}}} $ ，不是因为它可以在时间中解决 $ \ frac {n ^ 3} {2 ^ {\ sqrt {\ log n \ \}} $ “ 。如果你想使用“APSP可以在时间 $ \ dfrac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n \}） $ “拒绝猜想，您必须显示

$$ o（n ^ {3- \ delta}）\ cap \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}） }}=imptyset，$$ 或者，以简单的单词，没有功能 $ f \ in \ oomega（\ sqrt {\ log n}）$ 这样的 $ \ dfrac {n ^ 3} f \在o（n ^ {3- \ delta}）$ 。

好吧，事实上，另一个极端是真的。 $ \ dfrac {n ^ 3} f \ in o（n ^ {3- \ delta}）$ 所有 $ f \ in \ omega（\ sqrt {\ log n}）$ 。