Por que $ \ FRAC {n ^ 3} {2 ^ {\ Ômega (\ sqrt {\ log n})}} $ não refuta o limite inferior $ o (n ^ {3- \ delta}) $?

Question

Eu tenho um simples quesiton:

.

É conjetado que todo o caminho mais curto de pares (APSP) não tem $ o (n ^ {3- \ Delta)} $ -T -Time algoritmo para qualquer $ \ delta> 0 $ por seth.

também

.

Há um resultado que diz APSP pode ser resolvido no tempo $ \ frac {n ^ 3} {2 ^ {\ Ômega (\ sqrt {\ log n})}} $ por ryan williams .

Mas, esta melhoria não refuta as conjecturas.

Então, o que eu fiz é o seguinte: Eu comparo entre $ \ lim_ {n -> \ infty} \ frac {(\ frac {n ^ 3} {n ^ 3} {n ^} \ sqrt {\ log n}}})}}}} {n ^ {3- \ delta}}= 0 $ então, $ \ frac {n ^ 3} {2 ^ {\ Ômega (\ sqrt {\ log n})}} $ é melhor que o outro, então por que isso não significa que refutemos a conjectura.

Quando eu tiver esta função: $ \ frac {n ^ 3} {2 ^ {\ Ômega (\ sqrt {\ log n})}} $ , Eu não sabia como compará-lo com outro Desde o Big Omega é apenas por parte dele, como comparar em geral com outra função quando você tem este?

Obrigado antecipadamente!

Answer 1

A declaração "Não $ O (n ^ {3- \ Delta}) $ O algoritmo existe" (para qualquer constante $ \ delta> 0 $ ) significa que não há algoritmo que seja um fator polinomial mais rápido do que $ \ theta (n ^ 3) $ . Não exclui algoritmos que são mais rápidos por alguns menos do que o fator polinômio . Por exemplo, ele não exclui algoritmos com um tempo de execução de $ \ theta (\ frac {n ^ 3} {\ log n}) $ .

No seu caso, o conjunto $ 2 ^ {\ ômega (\ sqrt {\ log n})} $ inclui funções que crescem mais lentas do que qualquer polinômio. Por exemplo $ 2 ^ {\ sqrt {\ log n}} $ . Para ver isso, escolha qualquer constante $ \ epsilon> 0 $ e observe que:

$$ \ 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 fraty} 2 ^ {\ sqrt {\ log n} - \ epsilon \ log n}= 0. $$

Answer 2

Parece que a comparação na pergunta está errada.

$$ \ begin {alinhado} \ 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 ^ {+ \ fraty}= + \ fraty. \\ \ fim {alinhado} $$

Aqui $ \ log n $ é entendida como $ \ log_2n $ . Desde $ \ log_a n=log_a2 \ cdot \ log_2n $ , o limite acima ainda será infinito se a base de $ \ log $ é alternado para qualquer número maior que 1.

Na verdade, para qualquer constante $ c> 0 $ , porém menor do que é e qualquer constante $ \ delta> 0 $ , por mais pequeno, ainda temos, por argumento similar,

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

---

.

.

Eu comparo entre $ \ lim_ {n -> \ infty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \ \n^ {3- \ delta} \ \}= 0 $ Assim, $ \ frac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n})}} $ é melhor que o outro, então por que isso não significa que refutemos a conjectura.

Para ser mais cuidadoso, há outro erro no raciocínio acima. Mesmo se $ \ lim_ {n -> \ infty} \ dfrac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \n^ {3- \ delta} \ \}= 0 $ , não implica que ele refutará a conjectura. O ponto é, "APSP pode ser resolvido em tempo, $ \ dfrac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n \})}} $ " pode ser verdade, porque pode ser resolvido em tempo $ \ frac {n ^ 3} {2 ^ {0,01 \ sqrt {\ log n \ \}}} $ , não porque ele pode ser resolvido em tempo $ \ frac {n ^ 3} {2 ^ {\ sqrt {\ log n \ \}}} $ " . Se você quer usar o fato de que "APSP pode ser resolvido em tempo $ \ dfrac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n \}) }} $ "para refutar a conjectura, você tem que mostrar que

$$ O (n ^ {3- \ Delta}) \ Cap \ Frac {n ^ 3} {2 ^ {\ Ômega (\ sqrt {\ log n}) }}=FORTSET, $$ ou, em palavras simples, não há função $ f \ in \ ômega (\ sqrt {\ log n}) $ tal que $ \ DFRAC {n ^ 3} f \ in O (n ^ {3- \ delta}) $ .

Bem, na verdade, o outro extremo é verdadeiro. $ \ dfrac {n ^ 3} f \ em O (n ^ {3- \ delta}) $ para todos $ f \ in \ ômega (\ sqrt {\ log n}) $ .