HPC. Las propiedades de los digrafos de Cayley bigenerados relevantes para el problema de hamiltonicidad, cuya protección solicitamos en la segunda solicitud de patente (USPTO Application nº 13/570898), explicadas gráficamente.

Disclaimer. Republico esta entrada de hace unas semanas con algunas actualizaciones. Una es relevante pues hacemos avances para una definición más sencilla de la propiedad de smoothness o lisura.

He tenido que preparar estos gráficos (ciertamente  de bastante mala calidad) y los hago públicos dado que  muestran bien las diferentes propiedades cuyo testeo estoy intentando proteger en las diferentes claims.

Los ejemplos son ficticios y para simplificar los vértices se han etiquetado con números enteros en vez de con permutaciones. recordemos que el input es la permutación identidad  de grado n  y dos generadores (o permutaciones diferentes de la identidad del mismo grado). El problema es decidir (es decir no es interesa el problema de decisión) si un determinado par de generadores tiene recorridos hamiltonianos o no. Por convención, en los gráficos siguientes, la identidad es el  vértice etiquetado con el número 1. Los gráficos siguientes muestran claramente las propiedades estructurales de los Dígrafos de Cayley Bigenerados que son relevantes para el problema de hamiltonicidad.

I. Los test en concreto.

1.IAS regular, IAS Irregular.

Ignacio Reneses patent method. Example IAS regular and IAS irregularSi el par de generadores es no conmutativo o conmutativo pero obedece a unas propiedades aritméticas muy concretas, entonces será IAS regular, en cuyo caso tendrá unas propiedades más interesantes con respecto al problema de hamiltonicidad que si fuese irregular. Por otra parte las propiedades de hamiltonicidad de los casos conmutativos son bien conocidas y de hecho son los  que se utilizan en las aplicaciones (el toro de cualquier dimensión es una red de este tipo). Pero para la escala a la que se está empezando a trabajar, el ancho de banda / latencia que proveen las redes conmutativas, en mi opinión, se está empezando a quedar corto. Para poder aumentar ancho o latencia, tienen que aumentar el grado de los nodos (la dimensión del toro, por ejemplo), lo cual no es del todo interesante.

Una de las ventajas del método es que, para determinar las propiedades de hamiltonicidad, se evita construir todo el Digrafo de Cayley bigenerado. Es  suficiente trabajar con subdígrafos mucho más pequeños (aunque en el peor caso pueden tener tamaño subexponencial, concretamente la cota de Landau).

Teniendo en cuenta que a veces se tiene que trabajar con Dígrafos de Cayley del grupo simétrico o alternado que tienen respectivamente n ! o n!/2 vértices, esto ya supone un ahorro brutal en cuanto al uso de memoria.

Pero el ahorro en tiempo es  mucho más brutal, pues todos estos tests nos dan información sobre las propiedades de hamiltonicidad de los casos sin necesidad de aplicar un algoritmo exponencial de búsqueda.

Resumiendo, pasamos de una complejidad doblemente exponencial (en función del grado de las permutaciones) a una complejidad subexponencial  (idem). Nótese que los peores casos para nuestro método serán poco frecuentes.

Actualización 1 de diciembre de 2015.

2 (a). Propiedad de lisura / smoothness o retorcimiento / twisted.

No tengo todavía una definición de la definición de lisura lo más simplificada posible, aunque estoy empezando a pensar que posiblemente la definición más  simple implique la circunferencia. Vamos a desarrollar este tema en este punto. Primero algunos ejemplos.

A continuación un primer ejemplo twisted. Se indican los parámetros del caso en la propia figura. Se puede apreciar como los dos IASes diferentes del IAS de la identidad que pertenecen a la circunferencia están conectados por un tercer IAS diferente del de la identidad. Esto no podría pasar en un caso smooth.

Ignacio Reneses twisted case only one possible final vertex has hamiltonian traversals

Y un segundo ejemplo gráfico de otro caso.

 

Ignacio Reneses example twisted with no hamiltonian traversal.

En los dos casos anteriores, uno de los dos generadores es de orden 2.

Ahora un ejemplo de caso smooth o liso (como comentario al margen, si se plegase obtendríamos un toro y por lo tanto es localmente liso).

Ignacio Reneses smooth case

Quizás el lector se pregunte si haber casos twisted en los que ninguno de los dos generadores sean de orden 2 y cuales serían sus propiedades de hamiltonicidad. Diría que sí es posible que existan pero no serán difíciles. Tendría que volver a mirar la base de datos y revisar mis notas para contestar. Lo dejamos de momento como tema a investigar.

Fin de actualización 1 de diciembre de 2015. 

2 (b). Propiedade Entanglement o entrelazado.

Ignacio Reneses Patent Method. Entanglement property example

Nos hemos saltado la propiedad de smoothness o de ser liso, que normalmente se debería de testear antes, y para la  cual no tenemos gráfico recién realizado.

Si el caso es no entrelazado y además ninguno  de los dos generadores es una involución entonces tendrá unas propiedades de hamiltonicidad más ventajosas que si es entrelazado. Si es entrelazado entonces es posible que sea un caso complicado en sus propiedades de hamiltonicidad.

Actualización 1 de diciembre de 2015.

Un caso real entrelazado. Hemos hablado largo y tendido sobre este interesante caso en otras entradas. Tiene recorridos hamiltonianos en todos los vértices finales posibles pero en uno de ellos para encontrarlo hay que utilizar el backtraking. El IAS (en rojo) y el DAS (en verde) comparten una permutación además de la identidad. Se ve también la circunferencia.

Ignacio Reneses entangled case

Nótese que la autora o investigadora Ramyaa en su tesis habla de la propiedad de entrelazado pero no la relaciona con determinadas propiedades de hamiltonicidad. La señala en un momento dado como propiedad estructural pero no vuelve a hablar de ella.

Habla también de que si x e y son los generadores, cada uno de ellos genera un ciclo, y también xy^(-1) genera un ciclo. Queremos insistir en que este ciclo no es exactamente el mismo objeto que el IAS. Hay permutaciones que están incluidas en el IAS y no en el ciclo.

Por otra parte todas las variantes de su heurística (según el extracto siguiente queda claro que no se puede hablar de algoritmo, sino de heurística) requieren como paso previo que se instale en memoria el Digrafo de Cayley completo.

Extractos.

Although a random 2 regular digraph does not contain a lot of Hamilton cycles, Cayley graphs are very structured and most of them are Hamiltonian. It is reasonable to expect that randomized algorithms using the structure of Cayley graphs will have a good chance of finding Hamilton cycles. While this has proved to be true, i.e. increasing the restrictions which exploit more and more of the structure of Cayley graphs result in an increase in performance, most of the inherent structure was not captured by these algorithms.

La frase anterior destacada en negrita no puede ser más acertada. En nuestro caso pensamos que no solo hemos profundizado más identificando propiedades estructurales concretas relevantes para el problema de la hamiltonicidad, sino que defendemos que hemos identificado todas las relevantes, hemos descubierto sus mecanismos de operación y hemos descrito el modo como utilizarlas para resolver preguntas relacionadas con el problema de recorridos hamiltonianos. No estamos diciendo que hayamos resuelto todos los problemas abiertos en relación a los recorridos hamiltonianos en este tipo de dígrafos, sólo que gracias a los resultados de la patente ya se dispone de las herramientas adecuadas para resolverlos de manera eficiente.

They were unable to find Hamilton cycles in graphs with a very large number of vertices, even though they were Hamiltonian.

Fin de actualización.

3. Entrelazado por ciclos o cycle-entanglement.

La primera imagen muestra un caso, el A, que no es entrelazado por ciclos por el generador 1.  Y muestra un caso, el B, que es entrelazado por ciclos. Esto quiere decir que el IAS y el ciclo del generador comparten más de un arco. En el caso A, no entrelazado, sólo  comparten el arco 2–>1. En el caso B, entrelazado por el ciclo del generador 1, comparten los arcos 2–>1 y 4–>3.

Ignacio Reneses Patent Method. Cycle entanglement property example

En la imagen siguiente se muestra como  un caso puede ser entrelazado por un ciclo y no entrelazado por el otro. Por ello hay que testear esta propiedad por los dos ciclos. Se pueden dar los cuatro casos posibles:

–entrelazado por el ciclo del generador 1 y no entrelazado por  el generador 2.

–no entrelazado por el generador del ciclo 1 y entrelazado por el 2.

–no entrelazado por ninguno de los dos.

–entrelazado por los dos.

Ignacio Reneses patent method . Cycle entanglement property 2.

De nuevo esta propiedad  es muy relevante para el problema de hamiltonicidad.

Actualización 1 de diciembre de 2015.

A continuación un caso real entrelazado por los dos ciclos: un digrafo de Cayley del grupo cuaternio de orden 12.

Ignacio Reneses ejemplo real cycle entanglement Quaternion group of order 12Como se puede ver este caso se puede descomponer en 3 IAses, cada uno marcado con un color diferente. El IAS (marcado en color rojo) y el DAS se entrelazan en varios vértices, el 4, el 7 y el 10. Los dos ciclos están entrelazados, ya que contienen varios arcos de los diferentes IASes. En otra entrada hemos demostrado que los digrafos de Cayley de los grupos cuaternios serán en general entrelazados por ciclos.

Fin de actualización 1 de diciembre de 2015.

4. Circunferencia.

No hemos hablado de dos pasos del algoritmo que no son tests, sino que son puramente procedimientos que o bien nos dan información sobre un parámetro del dígrafo (el tamaño del IAS, que expresa el número máximo de vértices que potencialmente pueden ser vértices finales en un recorrido hamiltoniano) o bien permiten resolver el problema de decisión de ciclos hamiltonianos.

Y posteriormente a la patente, tal y como ya hemos  publicado múltiples veces en este mismo blog, hemos visto que hay otro parámetro clave que mostramos graficamente en la siguiente imagen. Como es casi obvio, para calcular este parámetro no hace falta construir toda la circunferencia. Ya hemos comentado en otras entradas como se puede obtener de manera rápida.

Circunferencia

II. La secuencia de tests.

Los tests descritos anteriormente se pueden hacer de manera independiente o en secuencia, añadiendo cada test información adicional al caso o input. En la  imagen siguiente se muestra la secuencia.

Secuencia de tests

En el gráfico anterior hay una errata y un “error” que no voy a corregir. El error es que por  definición los casos en los que un generador es una involución son entangled, y por lo tanto las casillas amarillas están mal puestas.

No estamos afirmando que esto sea la última palabra sobre este problema: quedan algunos flecos por resolver. Pero su solución tendrá que utilizar estas herramientas. Sí la segunda patente se hubiese concedido más rápidamente, seguramente muchos de ellos ya estarían resueltos.

III. Comentarios.

El  lector se preguntará: ¿ que tiene todo esto de idea abstracta ?. Parecen unos tests muy concretos, efectuados sobre un objeto muy concreto, un Digrafo de cayley bigenerado, y con unos resultados muy concretos, y con aplicaciones muy concretas en tecnología de redes.

Resulta que antes de mi investigación era completamente desconocido que cada uno de estos tests pudiesen ser tan relevantes para el problema  de hamiltonicidad, y por lo tanto el resultado es completamente nuevo.

Resulta que este problema de hamiltonicidad en Grafos de Cayley había sido estudiado seguramente por miles de investigadores de diversos campos (matemáticas, ingeniería  etc…;  incluyo a todos aquellos que han publicado sobre el problema de recorridos hamiltonianos en grafos o digrafos vértice transitivos) y no habían llegado al resultado ninguno de ellos (algunos de ellos muy brillantes por cierto; ojo, no digo que no haya habido otros avances, ni mucho menos, pero no eran mi resultado), y por lo tanto no es obvio.

Resulta, nos repetimos,  que cada uno de estos tests tiene importantes aplicaciones prácticas por  su relación con el problema de hamiltonicidad y por lo tanto es útil.

¿ Que son tests sencillos ? Sencillos de descubrir, para nada: ya hemos comentado que miles de investigadores han trabajado en el tema y no han visto la relación de estos tests con las propiedades de hamiltonicidad. Sencillos de ejecutar, sin duda (aunque para los tamaños de las redes que se utilizan en las aplicaciones hacerlos manualmente ya es prohibitivo). Pero si son sencillos de ejecutar, mejor que mejor. La sencillez o complejidad de un proceso no es condición para la concesión de una patente. El caso es que se cumple con los requisitos habituales que se piden para la concesión de  una patente. Sin embargo se han sacado de la manga a última hora la carta de la idea abstracta, que incluso aplicando el nuevo caso de Alice Corp. no es aplicable a mi solicitud.

La respuesta que vamos a presentar frente a la USPTO y cuya preparación me ha costado tres meses de trabajo es un documento de 60 páginas en el que, basándose en el documento Interim Guidance y en el documento de ejemplos basado en éstas, los dos emitidos por la USPTO, contiene todos los argumentos posibles para  demostrar que, si el Examinador comprendiese bien la innovación y siguiese estas instrucciones, la patente solicitada se debería de conceder, sí o sí. Le preguntaré a mi agente: si no ve problemas publicaré aquí mi respuesta de 60 páginas una vez hayamos presentado la respuesta, para que el lector pueda juzgar por sí mismo.

Predigo que una vez presentada, el Examinador no se va a leer en detalle el documento (soy consciente de que los Examinadores tienen poco tiempo; aunque sorprenda esto en el país que supuestamente lidera la innovación global, la USPTO, en relación con la cantidad de solicitudes que se presentan está sub-financiada:  por otra parte al  documento no le sobra una coma), que va a tardar más tiempo del que deberían en resolver mi respuesta a la final rejection y que mientras tanto se va cruzar por el camino otro caso judicial que va a afectar a mi solicitud de manera retroactiva (ya me ha pasado en dos ocasiones, con Bilski y con Alice Corp.), y de acuerdo con este nuevo caso la van a denegar de nuevo. Seguramente ya lo están preparando y ya me huelo la tostada sobre por dónde vendrán los tiros. No pueden alegar ausencia de novedad, obviedad, inutilidad ni que sea una idea abstracta. No les queda ninguna carta en este sentido y se tienen que sacar de la  manga alguna otra carta u obstrucción.

Actualización. Una entrada con las últimas novedades al respecto. Fin de actualización.

Otra posibilidad es que se conceda, ya que no tienen más remedio pero abran una vía de recurso administrativo posterior (tipo PTAB) en el que terceras partes puedan recurrir la concesión, variando la condición de novedad. Esta segunda posibilidad no me da ningún miedo ya que el resultado, cada uno de los tests, se mantendrá firme ante cualquier recurso.

Los abusos de poder propios de regímenes comunistas proteccionistas de su industria nacional, como está empezando a ser EEUU, son así.  La arrogancia de las grandes potencias, como EEUU, es así. Como soy más fuerte, impongo mis intereses, cueste lo  que cueste.

Nota. Lo que sigue ya no tiene por qué referirse necesariamente a mi invención. Fin de nota.

Hubo un tiempo en el que en este mismo país, en EEUU, si alguna invención era interesante, en vez de robarla utilizando como armas nuevos casos judiciales o nuevas regulaciones, sacaban el talonario y la compraban (no digo que este sea mi caso: podría ser  que finalmente la industria no se interese por  mi  invención).

Lamentablemente esto ha cambiado y ahora a las multinacionales de EEUU, amparadas por las nuevas regulaciones que han impulsado ellas mismas para protegerse, les sale más rentable aislarse del entorno innovador y robar las invenciones de los demás, en general pequeños inventores, a tutiplén.

P.s. Quiero añadir que  tras estar tres meses trabajando en el documento y estudiando todas estas materias, y siendo  justos, mi conclusión es  que hay  un problema real  con las ideas abstractas que a veces se patentan o intentan patentar, pero, tal y como ya han señalado muchos, la solución que han articulado no es la adecuada.

Tenían otras opciones y terceras partes se las indicaron (por ejemplo alegar falta de novedad u obviedad) pero optaron (desde luego no de manera inconsciente) por ir por la vía  de las ideas abstractas. ¿ Por qué ?. Porque esto les deja la puerta abierta a los examinadores para tomar decisiones arbitrarias. Y es lo que los diseñadores de las políticas públicas de innovación en EEUU quieren (lo que en principio cualquier poder desea): poder tomar decisiones arbitrarias. Esta sí, esta no, por que me sale de los cojones, y punto (pido disculpas por la expresión).

O quizás el problema no sea tanto la regulación (vía decisión judicial) en sí, sino como se está aplicando por la USPTO, como mi caso pone de manifiesto. Y eso que en las Interim Guidance y en los ejemplos está muy clara la intención. Si has decidido  no conocer a fondo una invención porque no tienes tiempo o por lo que sea, no la deniegues…

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: