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

Seré muy breve.

Ayer tuve un momento Poincaré. Al volver de la sobremesa de una cena, justo al entrar en un medio de transporte  se me ocurrió una posible solución al pregunta sobre cuantos niveles puede haber.

Creo que una cota superior del número de niveles debe de ser precisamente √n log n].  Por para n (grado de la  permutación) muy grande el numero de niveles se aproximará a esta cota. Si esto es correcto (y podría no serlo, podría quedarse en un espejismo Poincaré), queda por aclarar como se van construyendo los niveles superiores. Por otra parte de ser correcto sería muy relevante para la pregunta inicial que ha motivado esta serie de entradas: que pasa cuando el IAS se fija cómo igual a 2.

Cuando disponga de tiempo lo comprobaré y actualizaré la entrada.

Actualización 13/7/2013.

Que √n log n] es cota superior ahora  me parece casi evidente. El número máximo de vértices (permutaciones) del primer nivel es 2^√n log n] (esto es la cota de Landau). El del segundo nivel está en torno a 2^4 √n log n]. El del tercer nivel es 2^ c √n log n] con c una constante. Por lo tanto cada nivel añade una cierta cantidad (la constante c ¿ es la misma para todo n?) al factor. Y sabemos que √n log n] tiene que ser una cota superior (ya hemos visto que no está ajustada y que se puede mejorar), para todo n, de este factor. El proceso de generación de niveles no puede continuar indefinidamente y queda acotado por esta fórmula.

Y también parece claro que asintóticamente no será mucho menor (y, ojo, cómo en el caso anterior no hablamos exactamente de √n log n] sino de una cota más ajustada).

Ya hemos comentado en anteriores entradas que √n log n] se puede mejorar (recordemos que si se llegase a esta cota obtendríamos n^n que es superior a n).

Sigue abierto como se van construyendo los nuevos niveles.

Actualización 14/7/2013.

Al  margen de los establecido en la actualización anterior, parece claro que la además del orden de los dos generadores,  el orden del IAS o DAS (primer nivel), del orden de la circunferencia (segundo nivel), la secuencia de ordenes de los siguientes niveles caracterizan a un Dígrafo de Cayley bigenerado de Sn (y en general de cualquier grupo). Entiendo que cualquiera de estos ordenes es independiente de todos los demás, pero dejamos esto como pregunta.

En la actualización anterior nos interesábamos por el caso extremo en el que   el orden de todos los parámetros/niveles es el máximo posible. Y concluíamos que asíntoticamente los Dígrafos de Cayley bigenerados de Sn deben de tender a este caso extremo. La pregunta inicial que ha  originado toda esta serie de entradas es si hay infinitos casos que cumplan con la restricción de que fijemos sólo el orden primer nivel (haciéndolo igual a 2), pudiendo ser el resto de los ordenes (de los dos generadores y del resto de niveles) el máximo. Sobre esto una cosa está clara: si fijamos el orden del primer nivel (=2), entonces asintóticamente se necesitarán más niveles para llegar a n! que si no lo fijamos (y por lo tanto puede ser máximo). ¿ Llegará un momento en que esa cantidad de niveles de más estén por encima de la cota superior √n log n] ? Si así fuese entonces quedaría demostrado que no puede haber infinitos casos cuando  el  primer nivel queda fijo (=2 y seguramente si lo fijamos igual a cualquier constante).

Por supuesto para demostrar todo esto de manera rigurosa hay que pulir cuantitativamente todo lo que aquí estamos esbozando.

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: