Topología computacional

Una amplia familia de algoritmos relacionados con las 3-variedades gira en torno a la teoría de superficies normales , una expresión que engloba varias técnicas para convertir problemas de la teoría de 3-variedades en problemas de programación lineal entera.

• El algoritmo de reconocimiento de 3-esferas de Rubinstein y Thompson . Este algoritmo toma como entrada una 3-variedad triangulada y determina si la variedad es o no homeomorfa a la 3-esfera . Tiene un tiempo de ejecución exponencial en el número de símplices tetraédricos en la 3-variedad inicial, y también un perfil de memoria exponencial. Saul Schleimer demostró que el problema reside en la clase de complejidad NP . ^{[ 4 ]} Además, Raphael Zentner demostró que el problema reside en la clase de complejidad coNP, ^{[ 5 ]} siempre que se cumpla la hipótesis de Riemann generalizada . Utiliza la teoría de gauge de instantones, el teorema de geometrización de 3-variedades y el trabajo posterior de Greg Kuperberg ^{[ 6 ]} sobre la complejidad de la detección de nudos.
• La descomposición de suma de conexiones de 3-variedades también está implementada en Regina , tiene un tiempo de ejecución exponencial y se basa en un algoritmo similar al algoritmo de reconocimiento de 3-esferas.
• La determinación de que la 3-variedad de Seifert-Weber no contiene ninguna superficie incompresible ha sido implementada algorítmicamente por Burton, Rubinstein y Tillmann ^{[ 7 ]} y basada en la teoría de superficies normales.
• El algoritmo de Manning es un algoritmo para encontrar estructuras hiperbólicas en 3-variedades cuyo grupo fundamental tiene una solución al problema de palabras . ^{[ 8 ]}

Actualmente, la descomposición JSJ no se ha implementado algorítmicamente en software informático. Tampoco la descomposición de cuerpo de compresión. Existen algunas heurísticas muy populares y exitosas, como SnapPea , que ha tenido mucho éxito calculando estructuras hiperbólicas aproximadas en 3-variedades trianguladas. Se sabe que la clasificación completa de 3-variedades se puede hacer algorítmicamente, ^{[ 9 ]} de hecho, se sabe que decidir si dos 3-variedades cerradas y orientadas dadas por triangulaciones (complejos simpliciales) son equivalentes (homeomorfas) es recursivo elemental . ^{[ 10 ]} Esto generaliza el resultado sobre el reconocimiento de 3-esferas.

Determinar si un nudo es trivial se encuentra en las clases de complejidad NP ^{[ 12 ]} y co-NP . ^{[ 13 ]} El problema de determinar el género de un nudo en una 3-variedad es NP-completo ; ^{[ 14 ]} sin embargo, mientras que NP sigue siendo una cota superior para la complejidad de determinar el género de un nudo en R ³ o S ³ , en 2006 se desconocía si el problema algorítmico de determinar el género de un nudo en esas 3-variedades particulares seguía siendo NP-difícil . ^{[ 14 ]}

• Métodos computacionales para grupos homotópicos de esferas .
• Métodos computacionales para resolver sistemas de ecuaciones polinómicas .
• Brown tiene un algoritmo para calcular los grupos de homotopía de espacios que son complejos de Postnikov finitos , ^{[ 15 ]} aunque no se considera ampliamente implementable.

El cálculo de grupos de homología de complejos celulares se reduce a transformar las matrices de frontera a la forma normal de Smith . Si bien este problema está completamente resuelto algorítmicamente, existen diversos obstáculos técnicos para un cálculo eficiente en complejos grandes. Hay dos obstáculos principales. En primer lugar, el algoritmo básico de la forma de Smith tiene una complejidad cúbica en función del tamaño de la matriz involucrada, ya que utiliza operaciones de filas y columnas, lo que lo hace inadecuado para complejos celulares grandes. En segundo lugar, las matrices intermedias resultantes de la aplicación del algoritmo de la forma de Smith se completan incluso si se parte y se termina con matrices dispersas.

• Algoritmos eficientes y probabilísticos para la forma normal de Smith, como los que se encuentran en la biblioteca LinBox .
• Reducciones homotópicas sencillas para el preprocesamiento de cálculos de homología, como en el paquete de software Perseus .
• Algoritmos para calcular la homología persistente de complejos filtrados , como en el paquete TDAstats de R. ^{[ 16 ]}
• En algunas aplicaciones, como en el Análisis Topológico de Datos (ATD), es útil contar con representantes de clases de (co)homología lo más "pequeñas" posible. Esto se conoce como el problema de la localización de (co)homología. En variedades trianguladas, dada una cadena que representa una clase de homología, en general es NP-difícil aproximar la cadena homóloga de soporte mínimo. ^{[ 17 ]} Sin embargo, el caso particular de aproximar la localización de 1-cohomología en 2-variedades trianguladas es uno de los tres únicos problemas conocidos cuya dificultad es equivalente a la Conjetura de Juegos Únicos . ^{[ 18 ]}