Complejidad computacional. Cuando el orden del IAS queda fijo (6).

Tema a meditar durante el próximo viaje de avión que realizaré a finales de este mes: si todo lo que hemos apuntado en las anteriores entradas de esta serie es correcto (y el corolario es la contestación negativa a la pregunta inicial, es decir que  básicamente, para toda constante c, no hay infinitos casos tales que si el grado de la permutación es n, y el orden del grupo es Sn = n!, el orden el IAS pueda ser c; por ejemplo si c=2, a partir de un determinado n, no podrá haber casos con el |IAS| = c =2), entonces para n´s grandes hay un método rápido para identificar casos de grado n que no generen Sn (no se si ya existía esto). Recordemos que por el teorema de Dixon sabemos que a medida que el grado de la permutación, n, crece la proporción de pares de permutaciones que no generan Sn o An (el grupo alterno) tiende a cero. Por lo tanto, a priori, encontrar estos pares debería de ser cada vez más difícil.

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: