Warum $ \ frac {n ^ 3} {2 ^ {\ \ omga (\ sqrt {log n})}} $ widerheft nicht die untere Grenze $ o (n ^ {3- \ delta}) $?
-
29-09-2020 - |
Frage
Ich habe ein einfaches Quesiton:
Es wird vermutet, dass alle Paare kürzester Pfad (APSP) keinen
$ o (n ^ {3- \ Delta)} $ -time-Algorithmus für jede $ \ Delta> 0 $ von Seth.
auch
Es gibt ein Ergebnis, das besagt, dass APSP in der Zeit $ \ frac {n ^ 3} löst werden kann {2 ^ {\ omga (\ sqrt {\ log n})}}} $ von Ryan Williams .
aber diese Verbesserung widerstrebt die Vermutungen nicht.
so, was ich tat ist wie folgt: ich vergleichen zwischen $ \ lim_ {n -> \ fly} \ frac {(\ frac {n ^ 3} {2 ^ { \ sqrt {\ log n}}})}} {n ^ {3- \ Delta}}= 0 $ so, $ \ frac {n ^ 3} {2 ^ {\ Omga (\ sqrt {\ log n})}} $ ist besser als der andere, warum es nicht bedeutet, dass wir die Vermutung widerlegen.
wenn ich diese Funktion habe: $ \ frac {n ^ 3} {2 ^ {\ omga (\ sqrt {\ \ \ \ \ \ \ \ \ \ \ \ \ \ sqrt {\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s Ich wusste nicht, wie ich es mit anderen vergleichen sollte, da große Omega nur ein Teil davon ist, wie man im Allgemeinen mit anderer Funktion vergleicht, wenn Sie diese haben?
Vielen Dank im Voraus!
Lösung
Die Anweisung "NO $ O (N ^ {3- \ Delta}) $ Algorithmus ist vorhanden" (für jeden konstanten
In Ihrem Fall, der Set $ 2 ^ {\ Omega (\ Sqrt {\ log n})} $ enthält Funktionen, die langsamer werden als jedes Polynom. Beispielsweise $ 2 ^ {\ sqrt {\ log n}} $ . Um dies zu sehen, wählen Sie einen ständigen
$$ \ lim_ {n \ to \ fly} \ 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. $$
Andere Tipps
Es sieht so aus, als ob der Vergleich in der Frage falsch ist.
$$ \ beginnen {ausgerichtet} \ 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 {ausgerichtet} $$
Hier $ \ log n $ versteht sich als $ \ log_2n $ . Da $ \ log_a n=log_a2 \ cdot \ log_2n $ , die Grenze oben noch unendlich sein, wenn die Basis $ \ log $ ist auf eine beliebige Anzahl von mehr als 1 umgestellt.
In der Tat, für jede Konstante $ c> 0 $ , jedoch kleiner ist und eine beliebige Konstante $ \ delta> 0 $ , aber klein ist es, wir haben noch mit ähnlichem Argument
$$ \ lim_ {n \ to \ infty} \ frac {\ frac {n ^ 3} {2 {^ C \ sqrt {\ log n}}}} { \ \ \ {n ^ {3- \ delta} \ \ \ \ \ \ \ delta} \ \ \ \ \ \ \ \ delta \ flyy. $$
Ich vergleiche zwischen $ \ lim_ {n -> \ infty} \ frac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \ \n^ {3- \ delta} \ \}= 0 $ So \ frac $ {n ^ 3} {2 ^ {\ Omega (\ SQRT {\ log n})}} $ ist besser als der andere, warum es nicht bedeutet, dass wir die Vermutung widerlegen.
Um vorsichtiger zu sein, gibt es einen weiteren Fehler in der obigen Argumentation. Auch wenn \ $ lim_ {n -> \ infty} \ dfrac {\ frac {n ^ 3} {2 ^ {\ sqrt {\ log n}}}} {\ \n^ {3- \ DELTA} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 $ , es bedeutet nicht, dass es die Vermutung widerlegt. Der Punkt ist, "
$$ O (n ^ {3- \ delta}) \ cap \ frac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\nlog}) }}=\ yepset, $$ Oder in einfachen Wörtern gibt es keine Funktion $ F \ in \ Omega (\ sqrt {\ log n}) $ so, dass $ \ dfrac {n ^ 3 \ in o (n ^ {3- \ Delta}) $ .
Nun, tatsächlich ist das andere Extrem wahr. $ \ dfrac {n ^ 3} f \ in O (n ^ {3- \ delta}) $ für all $ f \ in \ omega (\ sqrt {\ log n}) $ .