Complejidad Computacional. La tercera posibilidad.

Desde hace varios meses quiero escribir una entrada sobre la materia de mi patente.

Los motivos son los siguientes:

–primero, en entradas anteriores hemos escrito largo y tendido sobre la posible complejidad computacional del problema de Recorridos Hamiltonianos en Digrafos de Cayley cuando el tamaño del input es el número de vértices y cuando el tamaño del input es el grado de la permutación. Hay al menos una tercera posibilidad de parámetro que se puede tomar cómo tamaño del input: el número de IAS (ver patente para la definición). En una eventual reducción de este problema a algún tipo de SAT esto se correspondería con el número de variables de la fórmula booleana.

–segundo, hay otra pregunta que me estoy planteando desde hace tiempo y para la cual no tengo respuesta. ¿ Hay infinitos casos tal que el de las permutaciones sea n, el orden n! o n!/2 (es decir grupo simétrico o alternado), tengan la propiedad smooth (ver patente),  y el orden  |IAS|=2,  o cualquier otra constante ?. Me oriento a pensar que no, que la c0ta inferior del orden del IAS debe de crecer a medida que n crece y que incluso debe de tender a 2^Raiz cuadrada [n log n], es decir debe de tender a acercarse a la cota superior. Hay alguna evidencia experimental de que esta cota superior no puede ser una constante (2 o cualquier otra), pero no puedo demostrarlo.

En cuanto que disponga de un poco de tiempo quiero investigar cual podría ser en este caso la complejidad computacional del problema citado.

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: