Warum $ \ frac {n ^ 3} {2 ^ {\ \ omga (\ sqrt {log n})}} $ widerheft nicht die untere Grenze $ o (n ^ {3- \ delta}) $?

Question

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!

Answer 1

Die Anweisung "NO $ O (N ^ {3- \ Delta}) $ Algorithmus ist vorhanden" (für jeden konstanten $ \ DELTA> 0 $ ) bedeutet, dass es keinen Algorithmus gibt, der ein Polynomfaktor schneller ist als $ \ theta (n ^ 3) $ . Es schließt keine Algorithmen aus, die von einem weniger weniger als Polynom Faktor schneller sind. Zum Beispiel schließt Algorithmen nicht mit einer Laufzeit von $ \ theta (\ frac {n ^ 3} {\ log n}) $ .

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 $ \ Epsilon> 0 $ und beachten Sie, dass:

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

Answer 2

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, " gelöst werden"{n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n \})}} $ “wahr sein könnte, weil es in der Zeit gelöst werden kann $ \ frac {n ^ 3} {2 ^ {0,01 \ sqrt {\ log n \ \}}} $ , nicht, weil es in der Zeit gelöst werden kann \ frac $ {n ^ 3} {2 ^ {\ sqrt {\ log n \ \}}} $ “ . Wenn Sie möchten, um die Tatsache nutzen, dass " gelöst werden kann" \ $ dfrac {n ^ 3} {2 ^ {\ Omega (\ sqrt {\ log n \}) }} $ "Um die Vermutung zu widerlegen, müssen Sie das zeigen

$$ 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}) $ .