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

Bueno ya tengo cada vez más clara la respuesta a alguno de los interrogantes que me planteaba en las anteriores entradas con el mismo título (aunque todavía no he podido sentarme a ver si experimentalmente es así; recordemos que para testar las ideas aquí hablamos ya de palabras mayores, o más bien de casos mayores, de 720 vértices…).

Para el tercer nivel, me quedo con la primera posibilidad. Construimos desde la Identidad el IAS, la Circunferencia, y el ciclo del generador de mayor orden (o de cualquiera de los dos si tienen el mismo orden), al que llamamos en lo que sigue el Ciclo.  Si construimos todas las Circunferencias de la Circunferencia de la identidad, cuando el n de Sn es grande obtendremos seguramente un “Toro” (ojo, no quiero decir con esto que esta parte del dígrafo se pueda empotrar en un toro) al que se le adjunta o pega un ciclo. Si en la permutación / vértice que se encuentre en medio del ciclo repetimos el mismo proceso obtendremos otro “Toro” y así hasta que finalice se llegue al ciclo que está pegado en medio de la primera circunferencia del IAS. Este es el tercer nivel.

Y de nuevo, si de la permutación que se encuentre a un cuarto del Ciclo de la Identidad construimos la misma estructura del tercer nivel, podremos obtener bien  una “Esfera” (si la intersección entre estas dos circunferencias  no es nula), bien  un “Toro”. Esta última forma será la asintóticamente general cuando el n de Sn sea lo suficientemente grande.

Un gráfico, no exactamente realista, dónde expongo lo explicado narrativamente arriba). Cómo se ve en el Toro que sale de la identidad hemos marcado la Circunferencia (segundo nivel). Cada polígono es un IAS (primer nivel). Si comparamos la identidad con la permutación correspondiente al vertice intermedio del primer Ciclo sabremos el “tamaño” del “Supertoro” (o “Superesfera”, en su caso) que obviamente está acotado por la Cota de Landau.

Nivel 3

Ahora mismo diría que todo debe de finalizar a este nivel,  ya que en este tercer nivel todos los vértices se encontrarán saturados. Si esto es así, n! debe de ser asintóticamente igual (asintóticamente aproximadamente igual) a la fórmula que permita contar (contar aproximadamente) el número de vértices de este “Supertoro”. La pregunta  es ¿ cual es el exponente, llamemosle X, que precede a Raíz Cuadrada [n log n] en esta supuesta fórmula de conteo ?.  Entiendo que no puede ser una constante y tiene que poder expresarse en función de n. Y surge la pregunta sobre si es posible que siendo el tercer nivel el último, este exponente no sea constante…

Repito, así es como veo el asunto ahora, pero no lo he comprobado experimentalmente y puede ser totalmente incorrecto.

Actualización (día siguiente):

La “ecuación” que tenemos que resolver por lo tanto es n! = e^X√n log n].

dónde el símbolo √ ] significa Raíz Cuadrada. Pongo ecuación entre comillas dado que no tiene mucho sentido plantearlo cómo ecuación pero nos sirve de momento para tener una idea de este factor.

¿ Cómo se resuelve una ecuación exponencial ? Un ejemplo:

Ecuaciones exponenciales

Aplicamos el mismo método a la nuestra ecuación pero solucionandolo más bien por acotación (seguimos utilizando e aunque en términos de complejidad computacional podríamos utiilizar igualmente 2 para simplificar):

log [n!] = log [e^X√n log n]

Por otra parte log [e^X√n log n] = X*√n log n]* log e. 

Log e = 1 y nos podemos olvidar de este factor.

Por lo tanto X= log [n!] / √n log n]

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] 

Y sustituyendo tendríamos entonces que n! = e^X  √n log n] = e^(√n log n]*√n log n]) = (según mathematica) = n^n, lo cual cómo era de esperar es incorrecto.

En efecto sabemos que (n/3)^n < n! < (n/2) ^n. Y de manera más exacta la fórmula de Stirling nos da que

stirling

De cualquier manera ya tenemos una idea del factor, claramente una cota superior y ahora hay que refinar el método para obtener una expresión del factor más exacta (o al menos una cota superior e inferior lo más exactas posibles).

Entonces surge la pregunta: conociendo más  o menos como es la cota, ¿ puede ser que sólo haya tres niveles ?

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: