HPC. Sobre la propiedad de lisura o smoothness en Dígrafos de Cayley Bigenerados: ¿ una caso que la falsifica ?II.

Nota. Salgo a una comida. Completaré la entrada más tarde, y seguramente la modificaré.

Seguimos la serie de entradas comentando sobre el método de la patente US 8266089 y sobre los tests incluidos en las 6 reclamaciones sustanciales (el resto son variaciones) de la solicitud de patente (de tipo continuation) 13/570898, de manera completamente injustificada por parte del examinador y que espero que finalmente se concedan en una próxima revisión. 

Ya hemos visto que no hay posibilidad de caso que falsee nuestro resultado, tal y cómo insinuábamos en el título. Nuestro resultado es robusto.

Pero sí creo que tras la sucesión de las últimas entradas la situación ha podido algo quedar confusa para el lector y quiero aclara las conclusiones principales del resultado:

1. Casi todos los Dígrafos de Cayley bigenerados son lisos o smooth y por lo tanto tienen recorridos hamiltonianos (en general varios, en general muchos) en todos los vértices finales posibles. Éste es el principal resultado de nuestra investigación y creo que es una buena noticia para los diseñadores de redes de interconexión. Esto que era completamente desconocido abre nuevas posibilidades al diseñador de redes, como diseñar redes en las que todo el enrutamiento se haga mediante recorridos hamiltonianos. Entiendo que habrá aplicaciones para las que este tipo de redes sea el más adecuado u óptimo. Teniendo esto en cuenta es altamente interesante disponer de un test que permita identificar los casos smooth. El test existe y lo hemos incluido como reclamación en la segunda solicitud de patente y por motivos que se me escapan (en la primera está claro, un formalismo legal; en la segunda, pese a la incidencia del caso Alice Corp. v CLS Bank, los motivos son completamente oscuros) se han rechazado.

2. El método que hemos presentado en la patente es secuencial pero es fácilmente paralelizable en la mayoría de sus etapas y sobre todo en la  que es computacionalmente más intensiva, tal y como hemos detallado en una anterior entrada.

3. Cuando por los motivos que sea al diseñador de redes de interconexión o de otro tipo, o a cualquier otro tipo de usuario le interesa (seguramente porque el caso tiene otras propiedades muy interesantes no relacionadas con la propiedad de hamiltonicidad) trabajar con un caso que no sea liso o smooth en el entorno de la identidad, y por lo tanto sea potencialmente complicado, no está todo perdido. El método de la patente incluye una serie de tests que permite identificar casos con propiedades estructurales diferentes a los que se puede aplicar técnicas diferentes.

Un caso que no es smooth es twisted. Por lo tanto según una primera clasificación todos los casos se pueden clasificar en smooth o en twisted. Quede claro que el hecho de que un caso sea twisted es señal de que es potencialmente difícil (es decir que puede contener vértices finales posibles sin recorridos hamiltonianos (a veces todos) o vértices finales posibles con recorridos hamiltonianos pero en poca cantidad y con elecciones que llevan a backtraking (hemos presentado un caso de éstos) pero no que lo sea necesariamente. Al día de hoy desconozco en que proporción los casos twisted son difíciles o fáciles. Pero dentro de esta clase twisted, existen tests adicionales, de nuevo basados en tests estructurales que nos permiten afinar más tanto el diagnóstico como el tratamiento, si el lector me permite la analogía médica. Estos tests adicionales se basan en el  hecho de que los casos twisted. Los twisted a su vez incluyen a los casos entangled y cycle entangled.     

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: