Caso retorcido o twisted de 120 vértices. Efectos de esta propiedad estructural sobre las propiedades de hamiltonicidad.

Añadido 22 octubre. Esta entrada está relacionada con las patentes USPATENT Nº 8266089 b2, concedida el 11 de septiembre de 2012 y USPATENT Nº 9697464 B2, concedida el 4 de julio de 2017.

En la imagen siguiente una representación gráfica de un caso de 120 vértices. Como se ve ya, para estos tamaños no hay una representación gráfica que sea especialmente clara.

El caso es twisted o retorcido (más concretamente lo que en otras entradas hemos llamado 2-twisted, aunque es una terminología que no tenemos claro que nos sea útil; hay que aterrizarla más). Vamos a utilizar esta imagen en el informe para ilustrar los efectos sobre las propiedades de hamiltonicidad de las propiedades estructurales. Realmente lo que estamos redactando en el informe aparecía ya en varias entradas de hace años. Simplemente lo estamos redactando de nuevo de la manera más clara posible y poniéndolo en un contexto más general. En este sentido esta entrada enlaza con ésta otra. Si en esa explicábamos a vista de pájaro el algoritmo general, que resuelve de manera eficiente todos los casos, en esta (en  el informe) lo vamos a explicar en detalle, lo cual exige comentar sobre los efectos de las diferentes propiedades estructurales y como utilizarlos para resolver de manera eficiente el problema de recorridos hamiltonianos.

a)Estado del arte previo a nuestra patente.

Recordamos en este párrafo cual era el estado del arte para resolver este problema antes de nuestra patente. El orden del IAS es 5 y por lo tanto el caso tiene 24 IASes. Encontrar un recorrido hamiltoniano en este caso por la fuerza bruta desinformada o de conocimiento grado cero implicaría explorar un árbol de 2^120 ramas (un número de unas 36 cifras). Y por la fuerza bruta algo informada (es decir el método sugerido por Housman de activar todos los IASes de todas las maneras posibles), implicaría explorar un árbol de 2^24 ramas (es decir 16777216 posibilidades). Esto último ya se pone complicado para hacerlo manualmente pero seguro que está al alcance de un PC y si no de un supercomputador. Pero ya hemos visto en la última entrada sobre computación cuántica que búsquedas desinformadas de unos 2^54 ya están por encima de las posibilidades de los más potentes superordenadores (con lo que la búsqueda de grado cero quedaría descartada, aunque no es necesaria). Antes de publicar nuestro resultado, el método sugerido por Hausman era el más eficiente, siendo determinista (es decir eficaz 100%, siempre decide el caso: o encuentra un recorrido hamiltoniano o demuestra que no puede existir). Para no complicarnos la vida ahora mismo con sutilezas de complejidad computacional, podemos calificar a este método de Housman, si el input se da en representación normal, es decir si el tamaño del input es el dígrafo completo (los 120 vértices) de subexponencial.  Si el input si diese en representación sucinta, por ejemplo en forma de generadores, su complejidad computacional sería obviamente mayor. Analizamos todo esto con más detalle en el informe. En cualquier caso, está claro que el método de Hausman no se puede considerar eficiente. 

b)Una imagen (algo confusa, pero difícil de mejorar) del caso.

Nota. Imprecisiones en la figura: 

Estamos trabajando con esta figura y vamos a anotar las imprecisiones que veamos. 

–Hay un arco azul del IAS 20 que une el vértice 103 con el 67 aunque en la figura parezca que se unen el 97 con el 67.

Fin de nota. 

En vez de utilizar etiquetas de los vértices semánticas, con permutaciones, se han utilizado etiquetas convencionales con números. Claramente al pasar de la etiqueta semántica a la convencional se pierde una de las posibilidades para corregir errores de conexión (comprobar que las dos permutaciones conectadas con un arco cumplen con la condición semántica). Los círculos marrones etiquetados (CX) identifican a los 6 IASes que pertenecen a la circunferencia de la identidad. Los diferentes IASes se diferencian por colores y también los hemos identificado del [1] al [24], rodeados por un cuadrado naranja.

Está claro que esto que mostramos como una representación gráfica de un grafo se puede mostrar por igual en forma de matriz. Y los parámetros y propiedades estructurales, que estamos mostrando en la representación gráfica,  se pueden expresar de manera equivalente en lenguaje de matrices.

c)Propiedades estructurales del caso.

Que el caso es twisted se puede ver por ejemplo con el IAS número 8 marrón, que conecta en ciclos de orden 2 con 2 IASes de la circunferencia de la identidad. Por vértice simetría está claro que esto no es la única manera en la que esta propiedad se puede manifestar.

Como estamos demostrando en el informe, el conocer esta propiedad estructural y sus efectos es clave para poder resolver de manera eficiente este tipo de casos. El uso de esta propiedad estructural para resolver el problema de recorridos hamiltonianos en este tipo de dígrafos de Cayley (en todos los 2-generados) está protegido por una claim de la segunda patente, concedida el 4 de julio de 2017.

Cuando los casos no tienen ninguna de estas propiedades (retorcimiento, entrelazado, entrelazado por ciclos) que pueden hacer que el problema de recorridos hamiltonianos sea complicado de resolver, entonces se dice que son smooth o lisos. Hay un test objetivo y eficiente (no se ahora mismo su complejidad computacional exacta pero pienso que debe de ser sublineal si el input es el dígrafo completo, pues exige al menos construir la circunferencia) que nos permite distinguir en el 100% de los casos si un caso es liso o no. Ya hemos publicado con detalles este test en el blog hace tiempo. Cuando un caso es liso tendrá abundantes recorridos hamiltonianos y será sencillo encontrarlos. La propiedad de smoothness o lisura y su uso para encontrar recorridos hamiltonianos está protegida por un claim de la segunda patente. 

 d)La solución que «se busca».

¿ Puede el lector determinar las propiedades de hamiltonicidad de este caso ?. No está garantizado que en este caso existan recorridos hamiltonianos. Si existen, se debe (cualquiera que quiera resolver el caso) de dar uno explicitamente. Si no existen, se debe de dar una demostración corta (es decir no vale dar el detalle de la exploración del árbol de 2^24 ramas). Corta no quiere decir de 4 lineas sino eficiente en función del tamaño. E interesaría (de no ser hamiltoniano el caso) un tipo de demostración de no hamiltonicidad que no sea ad-hoc, solo para este caso, sino un método de demostración eficiente aplicable a cualquier dígrafo de Cayley 2-generado.

Le damos al lector un pista, que el mismo podría obtener leyendo la patente: se puede limitar a buscar caminos que empezando en el vértice 1 (la identidad) terminen bien en el vértice 4, bien en el vértice 1.

d) Frontera teórica de los generadores para este caso. Como calcularla.

Recordamos que para resolver estos casos es importante (aunque no definitivo, no es lo más importante) tener en cuenta la región factible y sus fronteras. A continuación la tabla, extraída del informe, dónde se muestra las fronteras y región factible correspondiente a este caso. Hay una fórmula para calcular las fronteras teóricas. Si tenemos a x e y como los dos generadores con ordenes respectivos n y m, la fórmula es como sigue:

Frontera generador x = nº vértices del dígrafo / orden del generador y / orden del IAS.

Frontera generador y = nº vértices del dígrafo / orden del generador x / orden del IAS.

Cada fila de la tabla muestra una distribución (es decir un número de IASes activado por un generador y por el otro). Solo puede haber recorridos hamiltonianos en la región factible.

Nota. Frontera teórica. En la tabla siguiente decimos teórica dado que en la fórmula que hemos dado antes estamos asumiendo que es posible encontrar n IASes tal que cada uno de ellos tenga arcos en ciclos diferentes. Es decir tal que tomados dos a dos, los ciclos en los que están presentes los dos son todos ellos diferentes. Si  en un caso esto no fuese posible entonces lo que la fórmula indicaría sería una cota inferior: para que pueda haber un recorrido hamiltoniano, se necesitan activar al menos tantos como se indican en la frontera por un generador y por el otro. Fin de nota.  

Nº IASES ACTIVADOS POR EL GENERADOR DE ORDEN 2	Nº DE IASES ACTIVADOS POR EL GENERADOR DE ORDEN 4	RESULTADO
0	24	REGIÓN NO FACTIBLE. IMPOSIBLE OBTENER RECORRIDO HAMILTONIANO.
1	23	IDEM ANTERIOR
….	….	IDEM ANTERIOR
5	19	REGIÓN NO FACTIBLE. ACTIVANDO 19 IASES POR EL GENERADOR DE ORDEN 4, OBTENDREMOS AL MENOS UN CICLO DE ORDEN 4.
6	18	FRONTERA TEÓRICA DEL GENERADOR DE ORDEN 4. ACTIVANDO AL MENOS 6 IASES POR EL GENERADOR DE ORDEN 2 EVITAMOS CICLOS DEL GENERADOR DE ORDEN 4. INICIO REGIÓN FACTIBLE
7	17	REGIÓN FACTIBLE
8	16	REGIÓN FACTIBLE
9	15	REGIÓN FACTIBLE
10	14	REGIÓN FACTIBLE
11	13	REGIÓN FACTIBLE
12	12	FRONTERA TEÓRICA DEL GENERADOR DE ORDEN 2. ACTIVANDO AL MENOS 12 IASES POR EL GENERADOR DE ORDEN 4 EVITAMOS CICLOS DEL GENERADOR DE ORDEN 2. INICIO O FINAL REGIÓN FACTOBLE.
13	11	REGIÓN NO FACTIBLE. ACTIVANDO 13 IASES POR EL GENERADOR DE ORDEN 2 SE OBTENDRÁ AL MENOS UN CICLO DE ORDEN 2.
…	…	REGIÓN NO FACTIBLE
24	0	REGIÓN NO FACTIBLE

Está claro que cualquier algoritmo que se limite, para encontrar un recorrido hamiltoniano o demostrar que no existe, a explorar por fuerza bruta la región factible, no superará el estado de subexponencial. Aunque limitarse a explorar por fuerza bruta la región factible es mejor que explorar todo, está claro que esto no valdría como solución. Por otra parte explorar por fuerza bruta toda una distribución, no necesariamente de la región factible, ya se considera como eficiente. Aunque no es del todo satisfactorio…

Nota añadida 13 de septiembre 2019. La demostración más eficiente. No vamos a dar más detalles en esta entrada de lo que estamos escribiendo en el informe sobre este tema. En el informe estamos desarrollando el tema con pleno detalle. Pero lo comentado en el último párrafo ya es un pista clave para el lector, ya nos indica lo que sucede en estos casos dónde hay obstrucciones a la hamiltonicidad (obstáculo, concepto de la patente) y por dónde pueden ir los tiros para atacar este tipo de casos. Obviamente el objetivo final es evitar enfoques de fuerza bruta, aunque sea una fuerza bruta no exponencial.

Si una demostración de que todas las activaciones posibles de una distribución que no esté en la región factible generan contradicción (los cual demostraría a su vez que en este caso no es posible llegar a la región factible tal y como nos gustaría llegar si lo que buscamos es un recorrido hamiltoniano) viendo que pasa para cada una de las activaciones es suficiente, no  es del todos satisfactoria y se debe obtener una demostración de lo mismo que evite tener ver que pasa en cada una de las activaciones de esta distribución. Esta demostración que evite esto es el objetivo final para el lector…

Nótese que en el párrafo anterior cuando decimos «todas las activaciones posibles de una distribución…» no nos referimos a que se activen todos los IASes. Es suficiente que se activen los correspondientes al generador de menor orden y que realizando esto se genere una contradicción (algo incompatible con la existencia de  un recorrido hamiltoniano). Para comprender esto se puede leer la patente.   

Actualización 16 de octubre 2019. Este último párrafo ya nos da una idea de como puede ser un método general de demostración: primero, encontrar la frontera de los generadores, frontera que nos dice cual es el número mínimo de IASes que se deben de activar por un generador y por el otro (por ejemplo en el caso concreto que estamos describiendo, se puede ver que es condición necesaria de hamiltonicidad que al menos 6 IASes estén activados por el generador de orden 2) para que pueda haber un recorrido hamiltoniano. (esto es una condición necesaria de hamiltonicidad); segundo, demostrar que necesariamente, toda activación de menos de ese número mínimo de IASes por el generador de menor orden, nos lleva a contradicción (por ejemplo en el caso que nos ocupa se puede demostrar que toda activación de 5 IASes por el generador de orden 2 nos lleva a contradicción). Si se demuestra esto, que la condición necesaria no se puede cumplir, se demuestra que no puede haber recorridos hamiltonianos.  La contradicción se puede manifestar de diferentes maneras, por ejemplo demostrando que para toda activación se genera un ciclo de tamaño menor al número de vértices y otras. Y el hecho de que toda activación de ese número de IASes por el generador de menor orden genere contradicción se puede demostrar también de varias maneras, algunas menos eficientes (como por ejemplo en el caso que nos ocupa sería recorrer todas las combinaciones posibles de 5 IASes).

Damos las cifras de 5 y 6 más como ejemplo que como las reales de este caso. 

Que para determinar la hamiltonicidad al final haya que hacer en el peor caso una búsqueda no exponencial explica bien determinada fenomenología experimental que hemos detectado hace años (y que ya desde el primer momento nos pareció sorprendente):

–primero, que algoritmos de backtracking (como el que nosotros teníamos programado, o como el que utilizaron Ruskey y Effler en sus investigaciones) encuentren de manera relativamente rápidamente soluciones para casos como el que estamos describiendo. Aunque no sean conscientes de lo que sucede, al final estos algoritmos de backtraking, si están bien diseñados, acaban determinando la no hamiltonicidad explorando sólo una distribución.

–Y segundo, explica bien  que los casos en los que los métodos de Effler y Ruskey se atascaron no sean en general como estos que exploramos sino en general entrelazados por ciclos (cycle-entangled). Comprendo perfectamente que si se desconoce este rasgo estructural (y esto por varios motivos) la búsqueda pueda ser exponencial incluso en algoritmos de backtracking bien diseñados.  

Actualización 20 de octubre. 

El lector se preguntará si limitar este enfoque recién descrito a los ciclos de un solo generador no es demasiado limitado. Dicho de otra manera, si no puede haber casos en los que no aparezca una contradicción cuando se quiera evitar ciclos de un solo generador, pero pueda aparecer una contradicción con ciclos dónde intervienen dos generadores. Por ejemplo en el caso que analizamos un ciclo de estos (el más pequeño posible dónde intervienen 2 generadores) es el que cierra un IAS. Y, si en estos casos, no habría una frontera similar a la de los ciclos de un solo generador. En definitiva si no se puede generalizar el esquema de demostración indicado a ciclos mayores. Solo comentar que es una pregunta pertinente.

Fin actualizaciones 16 y 20 de octubre.      

Complejidad computacional de algoritmos que tienen que explorar por fuerza bruta toda una distribución. 

Por otra parte quizás el lector se pregunte, si el mejor algoritmo posible tuviese que recorrer necesariamente todas las activaciones de una distribución para decidir, cual sería la correspondiente complejidad computacional del problema. Nos hicimos esta pregunta hace tiempo, más por curiosidad que por otra cosa, y no encontramos una respuesta satisfactoria, ni tras breve reflexión nuestra ni tras búsqueda en internet.

Para que esté en P el uso del recurso tiene que estar acotado por un polinomio en concreto, con exponente fijo, no importa lo grande que sea este exponente. Sin embargo en este caso entiendo que el problema no queda acotado por un polinomio en concreto con exponente fijo, sino por infinitos polinomios con un exponente fijo pero que puede ser cada vez más grande. No se cual sería la correspondiente clase de complejidad en este caso. Esta es nuestra reflexión. 

Y esto es lo que se puede encontrar tras algunas búsquedas de internet.

Para ver que clase de complejidad le corresponde a este uso del recurso temporal habría que acotar la fórmula de (Combinaciones de n objetos en conjuntos de tamaño k).

Algo así intentan en esta entrada, pero no me quedan claras las conclusiones

https://stackoverflow.com/questions/24643367/whats-time-complexity-of-this-algorithm-for-finding-all-combinations

Y tampoco en esta otra entrada las respuestas son más claras. En la última de ellas dan una cota obvia de 2^n (que sería lo que se obtendría al tener que recorrer todas las distribuciones…), completamente insatisfactoria, ya que lo  que afirma es que la complejidad es exponencial, que no lo es. Si las cotas que dan no están claras, las clases de complejidad correspondientes tampoco lo están…

https://stackoverflow.com/questions/31120402/complexity-when-generating-all-combinations

En este otro enlace parecen insinuar que se tiene que considerar como tiempo polinómico.

https://skerritt.blog/big-o/

Lo decimos por la información que aparece en la tabla. 

The Big O Notation’s Order Of Growth
Constant	Logarithm	Linear	Polynomial	Exponential
O()	O($l$)	O($n$)	O(${\mathrm{n^}}^{}$), O(${\mathrm{n^}}^3$), O(${\mathrm{n^}}^{}$)	O(${\mathrm{2^}}^n$)

Como se ve consideran O(n^x) como polinómico. Esta era mi impresión inicial. Pero luego no elaboran sobre ello.

Terminamos con un último enlace y extracto: 

More generally: n choose k for any fixed constant k is Θ(n^k), because it’s equal to

n! / (k!(n – k)!) = n(n-1)(n-2)…(n-k+1) / k!

Which is a kth-degree polynomial in n with a nonzero leading coefficient.

La cota está clara. Pero, ¿ se puede concluir que un algoritmo con esta cota está en P ?

. Fin de nota.    

Cuando un caso tiene determinadas propiedades estructurales (las señaladas en las patentes) esto es causa de determinados efectos. Se trata de utilizar estos efectos para evitar la fuerza bruta…

Nota añadida 13 de septiembre 2019. El papel de las propiedades estructurales.

Las propiedades estructurales son clave para todo lo que venimos indicando. Para que en un determinado caso suceda lo que hemos comentado en la nota anterior de 13 de septiembre (es decir suceda el que para todas las activaciones posibles de una distribución fuera de la región factible se genere una contradicción, o dicho de una manera más sencilla, que el caso tenga un obstrucción a la hamiltonicidad), es condición necesaria que el caso tenga alguna de las propiedades estructurales señaladas en la patente. La que tiene este caso, retorcimiento u otras indicadas  en la patente.

Condición necesaria pero no suficiente. En este sentido podemos apuntar que (y podemos incluir los casos entrelazados por ciclo si tenemos en cuenta el orden de los generadores cuando son plegados) cuanto menor sea el orden de los generadores más posibilidades hay de que ocurran este tipo de obstrucciones. Como ya hemos visto  en otras entradas de hace años, los casos del tipo C2C3 (en los cuales podemos incluir al caso estudiado por Milnor; ojo, no nos olvidamos de los casos de Witte, que tenemos que encajar en todo esto; para ello tendríamos que leer el artículo en detalle) sobre los que apuntamos una teoría en otras entradas, los casos C2C4, C2C5, C3C3, dónde Cn indica el orden de cada uno de los dos generadores, serían los más complejos a este respecto de obstrucciones. En este sentido es seguro que se puede obtener un resultado general más ajustado que la propiedad de smoothness o lisura para determinar que casos no podrán tener obstrucciones. Es decir, ahora podemos afirmar que si un caso es smooth, entonces no puede tener obstrucciones. Pero es seguro que se podrá  obtener una proposición más fuerte del tipo: incluso si el caso no es liso o smooth, si el orden de los generadores es superior a tal y cual magnitud, entonces (para incluir a los casos cycle-entangled, se podría hablar del orden de los generadores una vez el caso sea plegado). Aunque incluso los casos con obstrucciones admiten una solución eficiente, el disponer de una proposición de este tipo sería muy interesante pues ahorraría trabajo, comprobaciones adicionales.   

. Fin de nota. 

Nota 14 de octubre 2019. Casos no hamiltonianos incondicionalmente y casos no hamiltonianos relativos a vértices finales.

En esta entrada estamos analizando un incondicionalmente no hamiltoniano. En este casos, simplificando mucho, independientemente del vértice final posible, el caso es no hamiltoniano. Por una parte, por la técnica de calcular la frontera se puede calcular que tienen que activarse un número mínimo de IASes por un determinado generador y por el otro; pero por otra parte se puede demostrar que cualquier selección posible de IASes activados por el generador de menor orden, de una distribución inferior a este número mínimo genera contradicciones. 

Pero hay casos que no son así. En estos otros casos, la no hamiltonicidad no es incondicional sino que depende del vértice final posible. Ya hemos analizado estos casos en entradas anteriores. En ellos, de nuevo simplificando mucho, lo que sucede es que al seleccionar un vértice final posible extremo (pensemos en el vértice final posible que generan los ciclos, pero no solo puede suceder en esto), el que activa el máximo posible de IASes por un determinado generador, o bien automáticamente ya nos estamos saliendo fuera de la región factible, o luego, se puede ver que activando el número de IASes necesario para entrar dentro de ésta, nos saldremos necesariamente. Aunque lo que sucede en estos casos es más evidente una vez que se conocen los conceptos de la patente, vamos a explicarlo todo esto en una sección del informe. En estos casos no hamiltonianos relativos a un determinado vértice final posible, sería de esperar que todos los VFs entre los dos extremos tuviesen recorridos hamiltonianos. En la imagen siguiente se muestra el caso que es de esperar y un par de casos reales que se salen de la expectativa. Las figuras muestran el IAS de la identidad. NO al lado de un vértice indica que en ese  vértice final posible no hay recorrido hamiltoniano. Un SI al lado de un vértice indica que en ese vértice final posible  sí hay recorrido hamiltoniano.  

Hay muchos más, aunque bastantes de ellos son entrelazados por ciclos. Este matiz es importante ya que en los entrelazados por ciclos, tal y como se explica en la patente, al ser plegados, puede aplicar el teorema de Rankin y su generalización por Curran, cuando en el original (el no plegado) no aplicaba. Esto puede explicar este fenómeno en estos casos. Pero no lo explica en los casos que no son entrelazados por ciclos. Estos son los que queremos explicar en detalle en el informe.     

Fin de nota. 

 

Nota final. Desarrollo del proyecto.  De hecho ya se solicitaba en la primera patente la protección del uso de las propiedades estructurales de manera individual para resolver el problema de recorridos hamiltonianos,  pero por cuestiones técnicas de normativa de la USPTO, por como se había planteado la primera patente, no se pudo conceder la protección individual en ese momento. El sistema es tan inflexible a este respecto que hubo que solicitar una segunda patente (una continuation) para proteger este territorio que es clave. En principio eran uno o 2 años más y con poco coste adicional. Pero se cruzó Alice Corp por medio, caso cuya solución judicial permitió a los examinadores de la USPTO actuar de manera completamente arbitraria, cosa que se confirmó ocurrió en nuestro caso. Como resultado 4 años más para la concesión de la continuation e inumerables dolores (informes que repetidamente el examinador no se ha leído) y dólares más también. En total, entre las dos patentes, 8 o 9 años y muchos, muchos, miles de dólares….

¿ Que valor tiene este derecho de propiedad ?. Muy poco o ninguno. Ahora tenemos investigadores que están utilizando nuestro resultado, sin pagar licencia ni ni siquiera mencionarnos, incluso pese a habérselo comunicado. No se han dignado ni a confirmar la recepción de los emails (lo cual por otra parte delata su culpabilidad). Y están apoyados por diversas organizaciones que, entre otras cosas, canalizan sus publicaciones. Estas organizaciones ven completamente normal que hagan esto y que ni hayan confirmado la recepción de los emails. 

Para evitar todo esto solo queda una solución: demandas judiciales a diestro y siniestro. Como pierda Trump las elecciones (o cualquier otro candidato republicano) vendrán de nuevo los «comunistas» de EEUU con nuevos criterios en contra de este tipo de propiedad y se puede esperar cualquier cosa. 

¿ Que nos queda por ver en este proyecto hasta llegar a buen puerto ?.

Quede claro que no somos los únicos afectados por la fase de arbitrariedad de la USPTO por el caso Alice Corp y por el escaso respeto que existe hacía las patentes como derecho de propiedad. Los hay a miles en esta situación.

Fin de nota