Por qué $ \ frac {n ^ 3} {2 ^ {\ _ _ \ sqrt {\ log n})}} $ no refuta el límite inferior $ O (n ^ {3- \ delta}) $?

Question

Tengo un simple Quesiton:

Se conyecta que todos los pares de ruta más corta (APSP) no tienen $ o (n ^ {3- \ delta)} $ -timoTM para cualquier $ \ Delta> 0 $ por Seth.

también

Hay un resultado que dice APSP se puede resolver en el tiempo $ \ frac {n ^ 3} {2 ^ {\ \ onga (\ sqrt {\ log n})}} $ por ryan williams .

Pero, esta mejora no refuta las conjeturas.

Entonces, lo que hice es lo siguiente: Me comparo entre $ \ lim_ {n -> \ infty} \ frac {(\ frac {n ^ 3} {2 ^ { \ sqrt {\ log n}}})} {n ^ {3- \ delta}}= 0 $ SO, $ \ frac {n ^ 3} {2 ^ {\ \ Onga (\ sqrt {\ log n})}} $ es mejor que el otro, entonces, por qué no significa que refutaremos la conjetura.

Cuando tengo esta función: $ \ frac {n ^ 3} {2 ^ {\ \ onga (\ sqrt {\ log n})}} $ , No sabía cómo compararlo con otros, ya que Big Omega solo está en parte de ella, ¿cómo comparar en general con otra función cuando tiene este?

¡Gracias de antemano!

Answer 1

La declaración "No $ o (n ^ {3- \ delta}) $ existe el algoritmo" (para cualquier constante $ \ Delta> 0 $ ) significa que no hay algoritmo que sea un factor polinomial más rápido que $ \ theTa (n ^ 3) $ . No excluye los algoritmos que son más rápidos por algunos menos que el factor polinomio . Por ejemplo, no excluye los algoritmos con un tiempo de ejecución de $ \ theTa (\ frac {n ^ 3} {\ log n}) $ .

En su caso, el conjunto $ 2 ^ {\ Omega (\ sqrt {\ log n})} $ incluye funciones que se cultivan más lentas que cualquier polinomio. Por ejemplo, $ 2 ^ {\ sqrt {\ log n}} $ . Para ver esto, elija cualquier constante $ \ epsilon> 0 $ y 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 \ infty} 2 ^ {\ sqrt {\ log n} - \ epsilon \ log n}= 0. $$

Answer 2

Parece que la comparación en la pregunta es incorrecta.

$$ \ comience {alineado} \ 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 -> \ tIty} 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 {alineado} $$

aquí $ \ log n $ se entiende como $ \ log_2n $ . Desde $ \ log_a n=log_a2 \ cdot \ log_2n $ , el límite superior aún será infinito si la base de $ \ log $ se cambia a cualquier número mayor que 1.

De hecho, para cualquier constante $ c> 0 $ , sin embargo, más pequeño es y cualquier constante $ \ delta> 0 $ , por pequeño que sea, todavía tenemos, por argumento similar,

$$ \ lim_ {n \ to \ infty} \ frac {\ frac {n ^ 3} {2 ^ {C \ sqrt {\ log n}}}} { \ \ \ {n ^ {3- \ Delta} \ \ \}}= + \ INFTY. $$

---

Me comparo entre $ \ lim_ {n -> \ infty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \ \n^ {3- \ Delta} \ \}= 0 $ So, $ \ frac {n ^ 3} {2 ^ {\ \ onga (\ sqrt {\ log n})}} $ es mejor que el otro, entonces, por qué no significa que refutaremos la conjetura.

Para ser más cuidadoso, hay otro error en el razonamiento anterior. Incluso si $ \ lim_ {n -> \ infty} \ dfrac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \n^ {3- \ Delta} \ \ \}= 0 $ , no implica que refutará la conjetura. El punto es que "APSP se puede resolver en el tiempo $ \ dfrac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ log n \})}} $ "podría ser cierto porque se puede resolver en el tiempo $ \ frac {n ^ 3} {2 ^ {0.01 \ sqrt {\ log n \ \}}}} $ , no porque se puede resolver en el tiempo $ \ frac {n ^ 3} {2 ^ {\ sqrt {\ log n \ \}}} $ " . Si desea utilizar el hecho de que "APSP se puede resolver en el tiempo $ \ dfrac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ log n \}) }} $ "Para refutar la conjetura, tiene que mostrar que

$$ O (n ^ {3- \ delta}) \ cap \ frac {n ^ 3} {2 ^ {\ _ onga (\ sqrt {\ log n}) }}=vacioset, $$ o, en palabras simples, no hay función $ f \ in \ omega (\ sqrt {\ log n}) $ de tal que $ \ dfrac {n ^ 3} f \ in o (n ^ {3- \ delta}) $ .

Bueno, de hecho, el otro extremo es cierto. $ \ dfrac {n ^ 3} F \ in o (n ^ {3- \ delta}) $ para todos $ f \ in \ omega (\ sqrt {\ log n}) $ .