لماذا $\فارك{n^3}{2^{\Omega(\sqrt{\log n})}}$ لا تدحض الأدنى $O(n^{3-\دلتا})$?

Question

لدي بسيط quesiton:

هو محدوس أن جميع أزواج أقصر طريق (APSP) لا $O(n^{3-\دلتا)}$-الوقت خوارزمية أي $\delta >0$ قبل سيث.

أيضا

هناك نتيجة لذلك أن يقول APSP يمكن حلها في الوقت المناسب $\فارك{n^3}{2^{\Omega(\sqrt{\log n})}}$ قبل ريان وليامز.

لكن هذا التحسن لا تدحض التخمين.

ذلك ما فعلته هو على النحو التالي:أقارن بين $\lim_{n -> \infty} \فارك{( \فارك{n^3}{2^{\sqrt{\log n}}})}{n^{3-\دلتا} } = 0 $ لذلك ، $\فارك{n^3}{2^{\Omega(\sqrt{\log n})}}$ هو أفضل من الآخر ، فلماذا هذا لا يعني أننا دحض التخمين.

عندما يكون لدي هذه الوظيفة: $\فارك{n^3}{2^{\Omega(\sqrt{\log n})}}$, لم أكن أعرف كيفية مقارنتها مع غيرها منذ الكبيرة أوميغا فقط على جزء منه ، كيفية مقارنة في العام مع وظيفة أخرى عندما يكون لديك هذا ؟

شكرا مقدما!

Answer 1

بيان "لا $O(n^{3-\دلتا})$ خوارزمية موجود" (أي ثابت $\delta>0$) يعني أنه لا يوجد خوارزمية a عامل متعدد الحدود أسرع من $\ثيتا(n^3)$.أنه لا يستبعد الخوارزميات التي هي أسرع من قبل بعض أقل من متعدد الحدود عامل.على سبيل المثال لا تستبعد خوارزميات مع وقت تشغيل $ heta(\فارك{n^3}{\log n})$.

في الحالة الخاصة بك ، $2^{\Omega(\sqrt{\log n})}$ وتشمل الوظائف التي تنمو أبطأ من أي متعدد الحدود.على سبيل المثال $2^{\sqrt{\log n}}$.أن نرى هذا اختيار أي ثابت $\ابسيلون>0$ و لاحظ أن:

$$ \lim_{n o \infty} \فارك{2^{\sqrt{\log n}}}{n^\ابسيلون} = \lim_{n o \infty} \فارك{2^{\sqrt{\log n}}}{2^{\ابسيلون \log n}} = \lim_{n o \infty} 2^{\sqrt{\log n} - \ابسيلون \log n} = 0.$$

Answer 2

يبدو وكأنه مقارنة في السؤال خطأ.

$$ \ ابدأ {محاذاة} \ lim_ {n -> \ infty} \ frac {\ frac {{^ {\ sqrt {\ sqrt {\ log n}}}} {\ \n^ {3- \ delta} \ \} &=lim_ {n -> \ infty} \ frac {\n^ {\ delta} {2 ^ {\ sqrt {\ log n}}}=lim_ {n - {n - {{n - infty} \ frac {2 ^ {\ delta \ تسجيل الدخول n}} {2 ^ {\ sqrt {\ log n}}} \\ &=lim_ {n -> \ enfty} 2 ^ {\ delta \ log n- \ sqrt {\ log n}}=lim_ {m -> {m -> {m -> {{\ delta m- \ sqrt {m} } \\ &=lim_ {m -> \ infty} 2 ^ {\ sqrt m (\ delta \ sqrt {m} -1)} \\ &= 2 ^ {+ \ Infty}= + \ Infty. \\ \ نهاية {محاذاة} $

هنا $ \ log n $ مفهوم ك $ \ log_2n $ . منذ $ \ log_a n=log_a2 \ cdot \ log_2n $ ، فإن الحد الأقصى أعلاه سوف لا يزال إنفينيتي إذا كانت قاعدة $ يتم تشغيل \ سجل $ إلى أي رقم أكبر من 1.

في الواقع، لأي ثابت $ c> 0 $ ، مهما كان أصغر وأي $ \ delta> 0 $ ، مهما كانت صغيرة، لا يزال لدينا، من خلال حجة مماثلة،

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

---

أنا قارن بين $ \ lim_ {n -> \ infty} \ frac {\ frac {{\ {\ sqrt {\ sqrt {\ log n}}}}}} {\ \ \n^ {3- \ delta} \ \}= 0 $ لذلك، $ \ frac {^ ^ {\ omega (\ SQRT {\ log n})}} $ أفضل من الآخر، فلماذا لا يعني أننا نضعح التخمين.

لتكون أكثر حذرا، هناك خطأ آخر في المنطق أعلاه. حتى لو كان $ \ lim_ {n -> infty} \ dfrac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}} {\ \n^ {3- \ Delta} \ \}= 0 $ ، فإنه لا يعني ذلك سوف يدحض التخمين. هذه النقطة هي "APSP يمكن حلها في الوقت المناسب $ \ dfrac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ log n \})} $ "قد يكون صحيحا لأنه يمكن حلها في الوقت المناسب $ \ frac {2 ^ {0.01 \ sqrt {\ log n \ \}}} $ ، ليس لأنه يمكن حلها في الوقت المناسب $ \ frac {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}) }}=emplyset، $ أو في كلمات واضحة، لا توجد وظيفة $ f \ in \ omega (\ sqrt {log n}) $ مثل $ \ dfrac {n ^ 3} f \ in O (n ^ {3- \ delta}) $ .

حسنا، في الواقع، الطرف الآخر صحيح. $ \ dfrac {n ^ 3} f \ in o (n ^ {3- \ delta}) $ لجميع $ F \ in \ Omega (\ sqrt {\ log n}) $ .