¿Por qué es esta función computable en tiempo

Mi libro de texto dice: "Definimos la función de la siguiente forma: f ( 1 ) = 2 y f ( i + 1 ) = 2 f ( i ) 1.2 . Tenga en cuenta que dado n , podemos encontrar fácilmente en O ( n 1.5 ) tiempo, el número i de tal manera que n se intercala entre f ( i ) y f ( i + $f\colon \mathbb{N}\to\mathbb{N}$$f(1)=2$$f(i+1)=2^{f(i)^{1.2}}$$n$$O(n^{1.5})$$i$$n$$f(i)$ ".$f(i+1)$

¿Cómo puedo convencerme de que podemos encontrar fácilmente en el tiempo O ( n 1.5 ) ? Como f se define de forma recursiva, creo que tenemos que calcular f ( 1 ) , f ( 2 ) , f ( 3 ) ... f ( j ) hasta f ( j ) ≥ n . Para saber el tiempo que tardan estos cálculos, creo que tenemos que encontrar un límite superior adecuado para i dependiente de $i$$O(n^{1.5})$$f$$f(1),f(2),f(3)\dots f(j)$$f(j)\geq n$$i$$n$y tenemos que encontrar un límite superior en el tiempo de ejecución de la función . Al final, esperamos poder mostrar la propuesta citada. Lamentablemente, no veo ni una cosa ni la otra.$x\to2^{x^{1.2}}$

Olvidé mencionar: Tenga en cuenta que estamos en un contexto no determinista. Entonces se afirma que es computable en O ( n 1.5 ) por una máquina de Turing no determinista.$f$$O(n^{1.5})$

Como algunas personas ya han leído esta pregunta, y algunas de ellas la encuentran útil e interesante también, pero nadie respondió hasta ahora, quiero proporcionar más información sobre el contexto: la afirmación citada es una parte integral de la prueba de El teorema de la jerarquía temporal no determinista. La prueba (con la afirmación) se puede encontrar, por ejemplo, en el libro de Arora y Barak , pero también he encontrado algunos otros recursos en la Web que presentan la misma prueba. Cada una de esas llamadas es fácil o trivial y no explica cómo encontrar en O ( n 1.5 ) . Entonces, o todos estos recursos que acabo de copiar de Arora y Barak o el reclamo no es tan difícil.$i$$O(n^{1.5})$

Denote por la longitud de un número x , es decir, ⌊ log 2 x ⌋ + 1 (para x > 0 ). Calcular 2 x requiere el tiempo O ( x ) en el modelo RAM, por lo que calcular f ( i + 1 ) a partir de f ( i ) lleva tiempo O ( f ( i ) 1.2 ) = O ( |$|x|$$x$$\lfloor \log_2 x \rfloor + 1$$x > 0$$2^x$$O(x)$$f(i+1)$$f(i)$ . Como f ( i ) está creciendo más rápido que geométricamente, el tiempo general para calcular f ( i + 1 ) es O ( | f ( i + 1 ) | ) . Como señala, debe hacerlo hasta f ( i + 1 ) ≥ n , lo que significa que f ( i ) < n . Por lo tanto, el tiempo total de ejecución es$O(f(i)^{1.2}) = O(|f(i+1)|)$$f(i)$$f(i+1)$$O(|f(i+1)|)$$f(i+1) \geq n$$f(i) < n$ .$O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$

En el modelo de máquina de Turing con una sola cinta, calcular lleva tiempo O ( x log x ) , por lo que el tiempo total de ejecución es O ( n 1.2 log n ) = O ( n 1.5 ) . El algoritmo para calcular 2 x reemplaza [ x ] por 1 [ [ x ] ] (aquí [ x ] es la representación binaria de x , y [ $2^x$$O(x\log x)$$O(n^{1.2} \log n) = O(n^{1.5})$$2^x$$[x]$$1[[x]]$$[x]$$x$ es la representación binaria que usa diferentes dígitos 0 ' , 1 ' ), y luego ejecuta repetidamente la transformación [ [ x ] ] ⟶ 0 [ [ x - 1 ] ] , que lleva tiempo O ( | x | ) = O ( log x ) .$[[x]]$$0',1'$$[[x]] \longrightarrow 0[[x-1]]$$O(|x|) = O(\log x)$