¿Por qué es tan difícil aplicar el Algoritmo de Haken a la teoría de nudos?

Question

¿Por qué es tan difícil aplicar el Algoritmo de Haken para reconocer si un nudo está deshecho? (¿Existe una implementación informática de este algoritmo?)

Answer 1

En cuanto al algoritmo de Haken: No es tan difícil de implementar (está esencialmente implementado en Regina, aunque por el momento hay que teclear unas cuantas líneas de python para pegar los bits; un único "gran botón rojo" está en camino). Sin embargo, es difícil ejecute ya que el algoritmo tiene un tiempo de ejecución exponencial (y, dependiendo de cómo se implemente, un uso exponencial de la memoria).

Hay dos hechos que hacen que el algoritmo de Haken sea más fácil de aplicar que muchos otros algoritmos de decisión de superficies normales:

• Sólo es necesario buscar en las superficies normales de los vértices, no en las superficies normales fundamentales (Jaco & Tollefson, 1995). Las superficies normales de vértice son mucho más fáciles (y rápidas) de enumerar.
• La prueba que se aplica a cada superficie normal de vértice es relativamente sencilla (ver si describe un disco con límite no trivial). Para otros problemas (en particular, la prueba de Hakenness), la prueba que se aplica a cada superficie normal de vértice puede ser mucho más difícil que la enumeración original de vértices.

La razón por la que el algoritmo de Haken es lento es que la enumeración de vértices es NP-difícil en general. Hay algunos atajos tentadores: uno es ejecutar $3^n$ programas lineales en tiempo polinómico que maximizan la característica de Euler sobre el $3^n$ posibles combinaciones de tipos de cuadrantes. Sin embargo, la experiencia experimental sugiere que este atajo empeora las cosas: resolver $3^n$ garantías de los programas lineales $\Omega(3^n)$ tiempo de ejecución incluso en el mejor de los casos para un nudo no trivial. Por otro lado, si se realiza una enumeración completa de vértices (y se estructura bien el código de enumeración de vértices [1]), en la práctica se suelen ver tiempos de ejecución mucho más rápidos, aunque el peor caso teórico sea más lento.

Un inciso (que ya se ha señalado anteriormente): existen pruebas heurísticas mucho más rápidas para el reconocimiento de nudos, aunque no siempre garantizan una respuesta definitiva. SnapPea tiene algunas, al igual que Regina. Hay muchas formas rápidas de demostrar que se tiene un nudo no trivial (por ejemplo, invariantes o estructuras geométricas). Una forma rápida de demostrar que tienes un nudo trivial es triangular el complemento y "simplificar ávidamente" esta triangulación. Si tiene suerte, obtendrá un toro sólido 1-tetraedro fácilmente reconocible. Si no se tiene suerte, hay que volver atrás y ejecutar el algoritmo de Haken. La observación interesante aquí es que, si tu simplificación codiciosa es lo suficientemente sofisticada, casi siempre tienes suerte. (Esto todavía se está escribiendo, pero véase arXiv:1011.4169 para experimentos relacionados con el reconocimiento de 3 esferas).

Por cierto, gracias Ryan por traerme a la red :)

[1] arXiv:0808.4050, arXiv:1010.6200

Answer 2

En primer lugar, me gustaría señalar que hay es un programa informático que sabrá si un nudo está deshecho, concretamente Jeff Weeks Snappea. No está rigurosamente probado que funcione tal cual, pero en la práctica siempre funciona.

La principal dificultad del algoritmo de Haken es el inmenso tamaño de los objetos que deben inspeccionar. Para un 3-manifold descrito pegando $n$ símplices juntas, hay $3^n$ problemas de programación entera representan cada posible superficie incompresible en la variedad, cada una de dimensión lineal en $n$ (los detalles dependen de cómo sea exactamente implementado). Cada uno de estos problemas de programación entera es un reto en sí mismo: cada uno tiene una base semigrupal finita para el conjunto de soluciones, pero el tamaño de la base crece exponencialmente con $n$ . El exponente de crecimiento es lo suficientemente alto como para que se vuelva rápidamente desesperante. Para diagramas de nudos sencillos, ya se sabe todo, y no tiene mucho sentido. Si se llega a diagramas de nudos con quizás 20 cruces, entonces habría quizás $3^{20} >$ 3.000 millones de problemas de programación entera, cada uno de ellos con muchísimas soluciones fundamentales con números enteros de quizá 100 dígitos que no son fáciles de identificar. Puede haber varios atajos y simplificaciones, pero las mejoras sólo aumentarán la complejidad de los múltiples que se pueden analizar.

En cambio, Snappea puede manejar fácilmente proyecciones de nudos con cien o doscientos cruces muy rápidamente, órdenes de magnitud más rápidamente que el tiempo que se tarda en dibujar el nudo.

Answer 3

Ben Burton ha aplicado el algoritmo de Haken en Regina. Él (y Rubinstein y Tillman) tienen un algoritmo funcional para determinar si una superficie normal en un triangulado 3-manifold es (in)compresible. No es terriblemente rápido, pero sí lo suficiente como para demostrar que el espacio de Seifert-Weber no contiene ninguna superficie incompresible. Este es un artículo reciente suyo en el arXiv: https://arxiv.org/abs/0909.4625

El principal problema es que el algoritmo de Haken consume mucha memoria. Si se ejecuta el algoritmo de Haken en la tabla de nudos Rolfsen/Conway, lo primero que hay que hacer es triangular el complemento del nudo. Las triangulaciones ideales eficientes se generan fácilmente mediante el algoritmo utilizado en SnapPea (originalmente debido a Thurston, por lo que yo sé). Pero a la teoría de superficies normales no le gustan del todo las triangulaciones ideales, así que lo que hace Regina es sustituir esa triangulación por una triangulación semisimplicial de una variedad compacta (el complemento de una vecindad tubular abierta del nudo). Esto hace que la triangulación sea decididamente menos eficiente. Creo que gente como Burton, Jaco y Rubinstein están trabajando para evitar este paso, pero no está completo.

En cualquier caso, hay que subdividir para llegar a un punto en el que la teoría de la superficie normal esté satisfecha. Regina puede recorrer las tablas de nudos, aplicando el algoritmo de Haken a cada nudo. En mi portátil completa la tabla de nudos en aproximadamente un día. Así que no es terriblemente lento. Pero a veces Regina está usando de 2 a 4Gb de RAM. Y creo que es en gran parte la enumeración normal de superficies lo que requiere la mayor parte del esfuerzo. Voy a ver si puedo conseguir Ben a comentar.