Complejidad Computacional. Cuando el orden del IAS queda fijo (4).

En la última entrada de esta serie ya hemos “resuelto” la ecuación que nos interesaba:

n! = e^X√n log n]

Recordemos que el símbolo √ ] es raíz cuadrada, e es e y por log entendemos el logaritmo natural. Finalmente señalar que la incógnita  de la ecuación  es X, el factor del exponente.

La solución es:

X= log [n!] / √n log n]

Y decíamos que como sabemos que  log [n!] = Theta (n log n), (Theta significa que si nos olvidamos de las constantes, la función n log n es cota superior e inferior de log n!), si convertimos (lo cual de nuevo no es muy correcto) esto en una igualdad nos daría

X= n Log n/√n log n] = √n log n] 

Esto significa que una cota superior de n! es e^(√n log n])^2 = n^n.

Ahora tenemos que utilizar esta información para contestar a las preguntas que nos interesan:

si un número finito constante de niveles es suficiente. Por la formula de X (la cota superior), parece que no puede haber un número constante de niveles. Sin embargo aquí lo interesante sería un procedimiento tal que, dado un n, nos permitiese acotar el número de   niveles que le  corresponden.   Y relacionado, ver como se pueden ir construyendo los niveles superiores.

–si puede haber infinitos caso con |IAS|=2

Preguntas que, con la información de que disponemos, pienso podemos intentar contestar ya.

P.s. Quizás para el lector todo esto que arriba figura no sea más que un encadenamiento de símbolos sin sentido. Pero para el que esto escribe, la forma del factor del exponente era algo sobre que llevaba preguntándose desde hace un par de años, pregunta a la que no ha podido dedicar tiempo para contestar. El EUREKA, que además llegó ayer sin esfuerzo (realmente no hacía falta mucho), tras como mucho una hora de trabajo de un caluroso domingo,  ha sido entonces de órdago. 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: