Duas funções , tais que mas

O título da pergunta expressa o que estou procurando - isso é para me ajudar a entender melhor os pré-requisitos para o Teorema da Hierarquia de Tempo Não Determinístico

Por exemplo, o livro Arora-Barak explica o teorema usando e - mas, eu posso ver que também! Portanto, estou tentando entender melhor o tempo "extra" garantido especificando que, para que seja um subconjunto adequado de , , não ... $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))$

Um exemplo é , .$g(n) = 2^{2^{n-1}}$$G(n) =2^{2^{n}}$

Temos , então .$g(n) = \sqrt{G(n)}$$g(n) = o(G(n))$

Enquanto isso, é claro, então , então$g(n+1) = G(n)$$g(n+1) = \Theta(G(n))$$g(n+1)\neq o(G(n))$

Por que duplicar exponencial? Quando adicionamos um a , queremos que o efeito seja mais do que uma constante multiplicativa (porque a notação grande esconde constantes multiplicativas e, portanto, aditivas). Vamos simplificar e dizer que queremos adicionar 1 em para ter um efeito polinomial no valor de . Quando você adiciona uma constante a :$n$$O$$n$$g(n)$$n$

• uma função linear é aumentada por uma constante aditiva

• uma função exponencial é aumentada por uma constante multiplicativa

• uma função exponencial dupla é aumentada polinomialmente (por uma potência de duas em nosso exemplo, portanto, )$g(n)^2 = G(n)$

Também podemos ter ,, etc., onde . Em geral, podemos deixar , em que e é não decrescente. Então nós temos:$g(n) = n^n$$g(n) = n!$$G(n) = g(n-1)$$g(n) = f(n)^n$$f(n) = \omega(1)$$f$

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

Então, mostramos usando a definição de limite (a última etapa é porque ). Portanto, funções como e até onde é a função inversa de Ackermann, também farão o truque para nós.$g(n) = o(G(n))$$f(n) = \omega(1)$$(\log\log n)^n$$\alpha(n)^n$$\alpha$

Toma $g(n)= n!$ e $G(n) = (n+1)!$.