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

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.

Esta entrada es continuación de la anterior con el mismo título.

1.Mejorando el estado del arte anterior a nuestras patentes.

En la entrada anterior hemos visto:

–que en este caso al activarse un cierto número de IASes por el generador de orden 2 se topa uno con una pared, una obstrucción a la hamiltonicidad insuperable, en una determinada distribución situada fuera de la región factible válida para los ciclos de un solo generador.

–que existe una estrategia de demostración eficiente (polinómica), pero insatisfactoria: realizar todas las activaciones posibles de todos los IASes por el generador de menor orden dentro de la distribución dónde topamos con la pared. Si el resultado de todas las activaciones posibles es una contradicción, queda demostrado que el caso no puede tener recorridos hamiltonianos (para esa elección de vértice final posibles).

2.Mejorando el método anterior, eficiente en teoría pero no del todo en la práctica.

a) La estrategia de demostración indicada ya pone este tipo de problemas en una determinada clase de complejidad, lo cual es notable teniendo en cuenta el estado del arte anterior. Pero obviamente también es insatisfactorio desde el punto de vista práctico. El hecho  de estar en esa clase no hace a un algoritmo práctico, ni mucho menos. Hay que dar un método más eficiente.

Para ello, el siguiente paso es identificar la causa de que pueda aparecer esta pared u obstrucción. Para que esta aparezca se tienen que dar dos condiciones necesarias: que se de una determinada propiedad estructural (por ejemplo que el caso sea retorcido; más en general que el caso no sea smooth); que se de un determinado orden de los generadores (por ejemplo que sean de orden pequeño).

Para ver que la existencia de la propiedad estructural es condición necesaria, se puede comparar el caso de 120 vértices que estamos analizando, con un caso de parámetros similares (que tenga generadores de ordenes similares) pero que sea smooth. Ya hicimos una comparación de estos dos casos en una entrada de hace años.

Para ver que la existencia de generadores con un determinado orden es necesaria, se puede comparar este caso con un caso que sea retorcido pero debido a que los generadores son de orden elevado, no se genera una obstrucción estructural a la hamiltonicidad. Para esto se pueden aportar múltiples casos.

b) Una vez analizado todo lo anterior quedará claro cual es el mecanismo que genera las obstrucciones y como utilizarlo para obtener una estrategia de demostración más eficiente de no hamiltonicidad que las señalada anteriormente. Esta estrategia básicamente es del siguiente tipo: demostrar que, debido a como opera el mecanismo de obstrucciones, si con una activación extrema (en algún sentido) dentro de una distribución, no se puede saltar la obstrucción, para todas las otras activaciones tampoco se podrá saltar, la situación será peor. Esto evita tener que probar con todas las activaciones posibles dentro de esa distribución. Y esto nos lleva a lo que hemos señalado en entradas anteriores: hay un tipo de secuencia de activaciones extrema tal que o bien nos hace obtener un recorrido hamiltoniano, o si no se puede conseguir esto con ella, se puede concluir automáticamente que no puede haber recorridos hamiltonianos para ese vértice final posible.

Siguiendo esta misma lógica, cuando un caso tiene obstrucciones en todos los vértices finales posibles, es decir cuando no tiene recorridos hamiltonianos (ni caminos ni ciclos), esto se podrá demostrar sin necesidad de hacerlo para todos los vértices finales posibles. La secuencia extrema incluye reglas que nos permitirán decidir cual es el vértice final posible por el que tenemos que empezar para que quede demostrado para todos los demás.

Nota. Lo descrito es solo uno de los enfoques que se pueden adoptar. Y está basado en lo que de verdad es clave en todo este asunto: saber que las propiedades estructurales son una de las condiciones necesarias de obstrucciones a la hamiltonicidad. Conociendo esto, todo lo demás se sigue. Y este conocimiento es precisamente lo que hemos querido proteger en las patentes. Fin de nota. 

Todo esto, que nos lleva a un método que además de eficiente en teoría es eficiente en la práctica, es lo que estamos intentando explicar en el informe de la manera más detallada y clara posible. Esto es mucho más satisfactorio que lo anterior, pero todavía insatisfactorio: el método es eficiente y práctico, pero partiendo del supuesto de que el tamaño del input es el dígrafo completo. Estos dígrafos pueden llegar a ser inmensos y el construirlos completos puede llegar a ocupar un gran espacio o memoria.

Es seguro que el método indicado en el punto anterior no es la última palabra. El último giro, que está por ver que sea posible, tiene que ser obtener una fórmula tal que solo conociendo los parámetros y propiedades estructurales, podamos determinar, sin necesidad de construir ni el dígrafo completo ni la secuencia extrema de activaciones, las propiedades de hamiltonicidad del caso.

3. El último giro: ¿ un método eficiente cuando el tamaño input viene dado de manera sucinta (por el grado de las permutaciones) ?. 

En entradas anteriores ya hemos comentado (tengo que revisarlas, ahora escribimos de memoria sobre ellas) que dados dos generadores en forma de permutaciones, se pueden obtener todos los parámetros del caso (es decir el orden de los generadores, el orden del IAS, el orden de la circunferencia..) de manera eficiente en función del grado de las permutaciones (es decir siendo este, el grado de las permutaciones, el tamaño del input).

Y en múltiples entradas anteriores hemos apuntado como, utilizando determinadas fórmulas, conociendo los parámetros, se pueden determinar las propiedades estructurales del caso. Aunque esto está inacabado pensamos que tiene que ser posible conseguir hacer esto de manera eficiente en función del grado de las permutaciones.

Si los parámetros y las propiedades estructurales se pueden determinar de manera eficiente en función del grado de las permutaciones (cosa que está por demostrar), entonces solo faltaría ver si con esto se puede determinar las propiedades de hamiltonicidad de los casos de manera eficiente en función del grado de las permutaciones. Si esto es posible, cosa que está por ver, ya habremos llegado al fondo. Imposible mejorar la  eficiencia más.

Este tiene que ser el objetivo final de la investigación, y aunque ya hemos realizado avances al respecto, está pendiente de completar.

Nota. Nótese que para dar este último giro, para encontrar un método eficiente cuando el tamaño del input es el grado de las permutaciones, entendemos que ya si que existirían importantes barreras (aunque de momento condicionales) de complejidad computacional, que no han existido para todos los pasos anteriores, perfectamente compatibles con los resultados condicionales más aceptados en esta disciplina.

A estos efectos recordamos por ejemplo el resultado de que el problema de minimal lenght generating sequence (que es básicamente un problema de camino más corto) para inputs dados en forma sucinta (no exactamente pero similares a que el tamaño del input fuese el grado de las permutaciones) es Pspace-complete para dígrafos de Cayley bigenerados. Por otra parte este mismo problema cuando el input es el dígrafo completo creo recordar que es NL-completo. Y sabemos que NL!=Pspace. Y uno, a priori, no esperaría que el problema RH fuese más sencillo que el del camino más corto…

Todo esto ya nos da una cierta idea de hasta dónde se puede llegar. No está descartado de momento que PSpace sea igual a P, pero si lo fuese (lo cual es improbable) no tengo nada claro cual es la clase de mínima complejidad dentro de P a la que Pspace podría ser igual.

–Sabemos que no puede ser igual a NL, ¿ pero a clases más potentes que NL y más débiles que todo P ?.

–sabemos que no puede ser igual a la jerarquía NC (que contiene a NL):  It is known that they lie outside of the class NC (a class of problems with highly efficient parallel algorithms), because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem.

Hemos escrito mucho en el blog sobre estos  temas, pero ahora mismo los tengo confusos. Volveremos a ellos en su debido tiempo.

Relevante.   

https://cstheory.stackexchange.com/questions/6753/what-is-the-big-version-of-nc

NCNC captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time O(logcn)O(logc⁡n) using O(nk)O(nk) parallel processors for some constants cc, kk. My question is if there is an analogous complexity class where time is ncnc and number of processors is 2nk2nk. As a fill-in-the-blank question:

NCNC is to PP as __ is to EXP

Creo que nos hicimos esta misma pregunta hace tiempo y no se si la llegamos a contestar. 

. Fin de nota.