Perché $ \ frac {n ^ 3} {2 ^ {\} omega (\ sqrt {\ log n})}} $ non confuta il valore inferiore $ o (n ^ {3- \ delta}) $?

Question

Ho un semplice QueSTon:

.

È congetturato che tutte le coppie il percorso più corto (APSP) non ha alcuna class class="container di matematica"> $ o (n ^ {3- \ delta)} $ algoritmo-tempo per qualsiasi $ \ delta> 0 $ di seth.

anche

.

C'è un risultato che dice che APSP può essere risolto in tempo $ \ frac {n ^ 3} {2 ^ {^}} {2 ^ {\ omega (\ sqrt {\ log n})}} $ di ryan williams .

Ma questo miglioramento non confuta le congetture.

Allora, ciò che ho fatto è come segue: Confronto tra $ \ lim_ {n -> \ infty} \ frac {(\ frac {n ^ 3} {2 ^ { \ sqrt {\ log n}}})} {n ^}} {n ^ {3- \ delta}}= 0 $ quindi, $ \ frac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n})}} $ è migliore dell'altro, quindi perché non significa che confutiamo la congettura.

Quando ho questa funzione: $ \ frac {n ^ 3} {2 ^ {^ omega (\ sqrt {\ omega (\ sqrt {\ log n})}} $ , Non sapevo come confrontarlo con altri poiché Big Omega è solo a parte, come confrontare in generale con altre funzioni quando hai questo?

Grazie in anticipo!

Answer 1

L'istruzione "No $ o (n ^ {3- \ delta}) $ L'algoritmo esiste" (per qualsiasi costante $ \ delta> 0 $ ) significa che non vi è un algoritmo che è un fattore polinomiale più veloce di $ \ theta (n ^ 3) $ . Non esclude gli algoritmi più veloci da alcuni meno del fattore polinomiale . Ad esempio non esclude gli algoritmi con un tempo di esecuzione di $ \ theta (\ frac {n ^ 3} {\ log n}) $ .

Nel tuo caso, il set $ 2 ^ {\ omega (\ sqrt {\ log n})} $ include funzioni che crescono più lentamente di qualsiasi polinomio. Ad esempio $ 2 ^ {\ sqrt {\ log n}} $ . Per vedere questo, scegli qualsiasi costante $ \ epsilon> 0 $ e notare che:

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

Sembra che il confronto nella domanda sia sbagliato.

$$ \ Begin {allineato} \ 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 {allineato} $$

qui $ \ log n $ è inteso come $ \ log_2n $ . Dal momento che $ \ log_a n=log_a2 \ cdot \ log_2n $ , il limite sopra sarà ancora infinito se la base di $ \ log $ è commutato su qualsiasi numero maggiore di 1.

Infatti, per qualsiasi costante $ c> 0 $ , per quanto più piccolo è e qualsiasi costante $ \ delta> 0 $ , Comunque piccolo è, abbiamo ancora, con argomento simile,

$$ \ LIM_ {n \ to \ INFTY} \ FRAC {\ FRAC {N ^ 3} {2 ^ {C \ SQRT {\ LOG N}}}} { \ \ \ {n ^ {3- \ delta} \ \ \}}= + \ Infty. $$

---

.

.

Confronto tra $ \ LIM_ {N -> \ INFTY} \ FRAC {\ FRAC {N ^ 3} {2 ^ {^ SQRT {\ LOG N}}}} {\ \ \n^ {3- \ delta} \ {3- \ delta}}}= 0 $ così, $ \ frac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ log n})}} $ è migliore dell'altro, quindi perché non significa che confutiamo la congettura.

Per essere più attento, c'è un altro errore nel ragionamento di cui sopra. Anche se $ \ lim_ {n -> \ \ infty} \ dfrac {\ frac {n ^ 3} {2 ^ {^ sqrt {\ log n}}}} {\ \n^ {3- \ delta} \ \}= 0 $ , non implica che confuterà la congettura. Il punto è: "APSP può essere risolto in tempo $ \ dfrac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ \ omega (\ sqrt {\ log n \})}} $ "Potrebbe essere vero perché può essere risolto in tempo $ \ frac {n ^ 3} {2 ^ {0.01 \ sqrt {\ log n \}}} $ , non perché può essere risolto in tempo $ \ frac {n ^ 3} {2 ^ {^ sqrt {\ log n \}}} $ " . Se si desidera utilizzare il fatto che "APSP può essere risolto in tempo $ \ dfrac {n ^ 3} {2 ^ {\ omega (\ sqrt {\ \ omega (\ sqrt {\ log n \}) }} $ "Per confutare la congettura, devi mostrarlo

$$ o (n ^ {3- \ delta}) \ cap \ frac {n ^ 3} {2 ^ {\}} {2 ^ {\ omega (\ sqrt {\ log n}) }}=vuoto, $$ O, in parole semplici, non c'è funzione $ f \ in \ omega (\ sqrt {\ log n}) $ tale che $ \ dfrac {n ^ 3} f \ in o (n ^ {3- \ delta}) $ .

Beh, infatti, l'altro estremo è vero. $ \ dfrac {n ^ 3} f \ in o (n ^ {3- \ delta}) $ per tutte le $ f \ in \ omega (\ sqrt {\ log n}) $ .