なぜ$ \ fRAC {n ^ 3} {2 ^ {\ OMEGA（\ sqrt {\ log n}）}}}}}}}}} $ $ O（n ^ {3- \ delta}）$を参照していませんか？

Question

私は単純な質問を持っています：

すべてのペアの最短パス（APSP）に $ o（n ^ {3- \ delta）} $ -timeアルゴリズムが $ \ delta> 0 $ によってseth。

も

APSPが時間 $ \ fRAC {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ によって Ryan Williams 。

しかし、この改善は推測を反論しません。

だから、私がしたことは次のとおりです。 $ \ lim_ {n - > \ fRac {（\ frac {n ^ 3} {2 ^ {）を比較します。 \ sqrt {\ log n}}}}}}}= 0 $ so、 $ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ は他のものより優れているので、なぜそれが推測を補うという意味ではありません。

この関数を持っているとき： $ \ frac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n}）}} $ Big OmegaはITの一部にのみ、この1つをお持ちの場合に一般的に比較する方法についてのみ、一般的に他の機能と比較する方法はありますか？

事前にありがとう！

Answer 1

ステートメント "no $ O（n ^ {3- \ delta}）$ アルゴリズムが存在する"（任意の定数 $ \ delta> 0 $ ）は、 $ \ theta（n ^ 3）より速く多項式係数のアルゴリズムはないことを意味します。 $ 。それは多項式因子よりもよりも速い、より速いアルゴリズムを除外しません。例えば、 $ \ theta（\ frac {n ^ 3} {\ log n}）$ の実行時間を持つアルゴリズムは除外されません。

あなたの場合、set $ 2 ^ {\ omega（\ sqrt {\ log n}）} $ には、多項式よりも遅くなる機能が含まれています。たとえば、 $ 2 ^ {\ sqrt {\ log n}} $ 。これを確認するには、定数 $ \ epsilon> 0 $ を選択して、次のように注意してください。

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

質問の比較が間違っているようです。

$$ \ begin {整列} \ lim_ {n - > \ infty} \ frac {\ frac {n ^ 3}}}}}} {\ \n^ {3- \ delta} \ \ \ \ \ \} lim_ {n - > \ infty} \ frac {n ^ {\ delta}}}} {2 ^ {\ sqrt {\ log n}}}=lim_ {n - > \ infty} \ frac {2 ^ {\ delta \ {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} -1} \\ ＆= 2 ^ {+ \ infty}= + \ infty。\\ \ end {aligned} $$

ここに $ \ log n $ は $ \ log_2n $ として理解されています。 $ \ log_a n=log_2 \ cdot \ log_2n $ 以降、 $の基底が依然として無限大になるでしょう。 \ log $ は、1を超える任意の数に切り替わります。

実際には、任意の定数 0 $ の場合、それが小さく、定数 $ \ delta> 0 $ が小さいですが、同様の議論によって、

のまだ持っています

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

---

$ \ lim_ {n - > \ infty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}}} {\ \ \n^ {3- \ delta} \ \ \ \}= 0 $ so、 $ \ frac {n ^ 3} {2 ^ {\ ormega（\ SQRT {\ log n}）} $ は他のものより優れているので、なぜそれが推測を補うという意味ではありません。

上記の推論には別の間違いがあります。 $ \ lim_ {n - > \ infty} \ dfrac {\ frac {n ^ 3}} {\ log n}}}}}}}}}}}}}} ^ {3- \ delta} \ \ \}= 0 $ 、それは推測を理解することは意味がありません。 POINTは、「APSPは時には解決できます。 $ \ dfrac {n ^ 3} {2 ^ {\ omega（\ sqrt {\ log n \}）}}}}}}}}}}}}スパン>>数学・コンテナ "」それは時間内に解くことができるので、スパンクラス= <真のかもしれません" $ \ FRAC {N ^ 3} {2 ^ {0.01 \ SQRT {\ログの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}） \ \ hempyset、$$ あるいは、プレーンな単語では、関数はありません $ f \ in \ on kega（\ sqrt {\ log n}）$ そのような $ \ dfrac {n ^ 3} f on o（n ^ {3- \ delta}）$ 。

ええと、実際には、他の極端なものは当てはまります。 $ \ dfrac {n ^ 3} f on o（n ^ {3- \ delta}）$ すべての $ f \ in \ on kega（\ sqrt {\ log n}）$ 。