Почему $ \ frac {n ^ 3} {2 ^ {\ Omega (\ SQRT {\ log n})}} $ не опровергает нижнюю границу $ O (n ^ {3- \ delta}) $?

Question

У меня простой Quesiton:

ГНЕЖНУЮ, что все пары кратчайший путь (APSP) не имеют $ O (n ^ {3- \ delta)} $ Algorithtime для любого $ \ Delta> 0 $ by seth.

также

Есть результат, который говорит, что говорит APSP во времени $ \ FRAC {N ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n})}} $ by Райан Уильямс .

Но это улучшение не опровергает гипотезы.

Итак, что я сделал так: я сравниваю между $ \ lim_ {n -> \ infty} \ frac {(\ frac {n ^ 3} {2 ^ { \ sqrt {\ log n}}})} {n ^ {3- \ delta}}= 0 $ Итак, $ \ frac {n ^ 3} {2 ^ {\ Omagega (\ sqrt {\ log n})}} $ лучше другого, так почему это не значит, что мы опровергаем гипотезу.

Когда у меня есть эта функция: $ \ frac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n})}} $ , Я не знал, как его сравнить с другими, так как Big Omega только на его части, как сравнивать в целом с другой функцией, когда у вас есть этот?

Спасибо заранее!

Answer 1

Заявление «Нет $ O (N ^ {3- \ Delta}) $ Algorither существует" (для любой постоянной $ \ delta> 0 $ ) означает, что алгоритм нет, который является полиномиальным фактором быстрее, чем $ \ theta (n ^ 3) $ . Это не исключает алгоритмы, которые быстрее по некоторым меньше, чем полиномиальный фактор. Например, он не исключает алгоритмы с течением работы $ \ Theta (\ frac {n ^ 3} {\ log n}) $ .

В вашем случае набор $ 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 {rocureded} \ 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 {выровненный} $$

Здесь $ \ log n $ понимается как $ \ log_2n $ . Поскольку $ \ log_a n=log_a2 \ cdot \ log_2n $ , предел выше все равно будет бесконечность, если база $ \ log $ переключается на любое число больше 1.

Фактически, для любой постоянной $ C> 0 $ , однако меньший это и любая постоянная $ \ Delta> 0 $ , однако, маленький, у нас все еще есть, по аналогичным аргументу,

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

---

Я сравниваю между $ \ lim_ {n -> \ infty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \ \n^ {3- \ delta} \ \}= 0 $ Итак, $ \ frac {n ^ 3} {2 ^ {\ 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 {N ^ 3} {2 ^ {0,01 \ SQRT {\ log n \ \}}} $ , не потому, что его можно решить во времени $ \ frac {n ^ 3} {2 ^ {\ sqrt {\ log n \ \}}} $ " , Если вы хотите использовать тот факт, что «APSP может быть решен во времени $ \ dfrac {N ^ 3} {2 ^ {\ omagega (\ sqrt {\ log n \}) }} $ "Чтобы опровергнуть гипотезу, вы должны показать, что

$$ o (n ^ {3- \ delta}) \ cap \ frac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n}) }}=Edityset, $$ Или, на простых словах, нет функций $ f \ in \ omagega (\ 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}) $ .