Zwei Funktionen , so dass aber

Der Titel der Frage drückt aus, wonach ich suche - dies soll mir helfen, die Voraussetzungen für den Satz der nichtdeterministischen Zeithierarchie besser zu verstehen

Zum Beispiel erklärt das Arora-Barak-Buch den Satz mit und - aber ich kann das auch sehen! Ich versuche also besser zu verstehen, welche "zusätzliche" Zeit garantiert ist, indem ich spezifiziere, dass eine richtige Teilmenge von , , nicht ... $g(n) = n$$G(n) = n^{1.5}$$n \in o(n^{1.5})$$\text{NTIME}(g(n))$$\text{NTIME}(G(n))$$g(n + 1) = o(G(n))$ $g(n) = o(G(n))$

Ein Beispiel ist $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

Wir haben $g(n) = \sqrt{G(n)}$, damit $g(n) = o(G(n))$.

Inzwischen natürlich $g(n+1) = G(n)$ damit $g(n+1) = \Theta(G(n))$, damit $g(n+1)\neq o(G(n))$

Warum doppelt exponentiell? Wenn wir eins hinzufügen$n$Wir wollen, dass der Effekt mehr als eine multiplikative Konstante ist (weil groß $O$Notation verbirgt multiplikative und damit additive Konstanten). Machen wir es uns einfach und sagen wir, dass wir 1 hinzufügen möchten$n$ einen polynomiellen Effekt auf den Wert von haben $g(n)$. Wenn Sie eine Konstante hinzufügen$n$::

• Eine lineare Funktion wird um eine additive Konstante erhöht

• Eine Exponentialfunktion wird um eine multiplikative Konstante erhöht

• Eine doppelte Exponentialfunktion wird polynomiell erhöht (in unserem Beispiel also um eine Zweierpotenz) $g(n)^2 = G(n)$)

Wir können auch haben $g(n) = n^n$, $g(n) = n!$usw., wo $G(n) = g(n-1)$. Im Allgemeinen können wir lassen$g(n) = f(n)^n$, wo $f(n) = \omega(1)$ und $f$nimmt nicht ab. Dann haben wir:

$$\lim_{n\to\infty} \frac{g(n)}{G(n)} = \lim_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim_{n\to\infty}\frac{1}{f(n)} = 0$$

Also haben wir gezeigt $g(n) = o(G(n))$ Verwenden der Grenzwertdefinition (der letzte Schritt ist weil $f(n) = \omega(1)$). Daher funktioniert wie$(\log\log n)^n$ und selbst $\alpha(n)^n$ wo $\alpha$ ist die inverse Ackermann-Funktion, wird den Trick auch für uns tun.

Nehmen $g(n)= n!$ und $G(n) = (n+1)!$.