La topología algorítmica, o topología computacional, es un subcampo de la topología que se superpone con áreas de la informática, en particular, la geometría computacional y la teoría de la complejidad computacional.

Una preocupación principal de la topología algorítmica, como su nombre lo sugiere, es desarrollar algoritmos eficientes para resolver problemas que surgen naturalmente en campos como la geometría computacional, los gráficos, la robótica, las ciencias sociales, la biología estructural y la química, utilizando métodos de la topología computable.

Principales algoritmos por área temática

Teoría algorítmica de 3 variedades Una gran familia de algoritmos relacionados con las 3-variedades giran en torno a la teoría de superficies normales, que es una frase que engloba varias técnicas para convertir problemas de la teoría de 3-variedades en problemas de programación lineal entera.

Algoritmo de reconocimiento de tres esferas de Rubinstein y Thompson. Este es un algoritmo que toma como entrada una variedad triangulada de 3 dimensiones y determina si la variedad es homeomorfa o no a la variedad de 3 dimensiones. Tiene un tiempo de ejecución exponencial en el número de símplex tetraédricos en la variedad 3 inicial y también un perfil de memoria exponencial. Además, está implementado en el paquete de software Regina. Saul Schleimer continuó demostrando que el problema radica en la clase de complejidad NP. Además, Raphael Zentner demostró que el problema reside en la clase de complejidad coNP, siempre que se cumpla la hipótesis de Riemann generalizada. Utiliza la teoría de calibre instantáneo, el teorema de geometrización de 3 variedades y el trabajo posterior de Greg Kuperberg sobre la complejidad de la detección de nudos. La descomposición de suma conexa 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. Burton, Rubinstein y Tillmann han determinado algorítmicamente que la 3-variedad de Seifert-Weber no contiene ninguna superficie incompresible, basándose 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 verbal.

Actualmente, la descomposición JSJ no se ha implementado algorítmicamente en software de computadora. Tampoco la descomposición del cuerpo por compresión. Hay algunas heurísticas muy populares y exitosas, como SnapPea, que tiene mucho éxito al calcular estructuras hiperbólicas aproximadas en variedades trianguladas de 3 elementos. Se sabe que la clasificación completa de 3-variedades se puede hacer algorítmicamente, de hecho, se sabe que decidir si dos 3-variedades cerradas y orientadas dadas por triangulaciones (complejos simpliciales) son equivalentes (homeomórficas) es recursivo elemental. Esto generaliza el resultado del reconocimiento de 3 esferas.

Algoritmos de conversión

SnapPea implementa un algoritmo para convertir un nudo plano o un diagrama de enlace en una triangulación cuspide. Este algoritmo tiene un tiempo de ejecución aproximadamente lineal en el número de cruces en el diagrama y un perfil de memoria bajo. El algoritmo es similar al algoritmo de Wirthinger para construir representaciones del grupo fundamental de complementos de enlace dados por diagramas planares. De manera similar, SnapPea puede convertir presentaciones quirúrgicas de 3 variedades en triangulaciones de las 3 variedades presentadas. D. Thurston y F. Costantino tienen un procedimiento para construir una variedad 4-triangulada a partir de una variedad 3-triangulada. De manera similar, se puede utilizar para construir presentaciones quirúrgicas de 3-variedades trianguladas, aunque el procedimiento no está escrito explícitamente como un algoritmo; en principio, debería tener un tiempo de ejecución polinomial en el número de tetraedros de la triangulación de 3-variedades dada. S. Schleimer tiene un algoritmo que produce una variedad triangulada de 3 dimensiones, dada como entrada una palabra (en generadores de torsión Dehn ) para el grupo de clases de mapeo de una superficie. La variedad 3 es la que utiliza la palabra como mapa de unión para una división de Heegaard de la variedad 3. El algoritmo se basa en el concepto de triangulación en capas.

Teoría de nudos algorítmicos Se sabe que la determinación de si un nudo es trivial o no se realiza en las clases de complejidad NP así como también en las co-NP. Se sabe que el problema de determinar el género de un nudo tiene la clase de complejidad PSPACE.

Homotopía computacional

Métodos computacionales para grupos de homotopía 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, aunque no se considera ampliamente implementable.

Homología computacional El cálculo de los grupos de homología de los complejos celulares se reduce a llevar las matrices límite a la forma normal de Smith. Aunque este es un problema completamente resuelto algorítmicamente, existen varios obstáculos técnicos para el cálculo eficiente de complejos grandes. Hay dos obstáculos centrales: En primer lugar, el algoritmo básico de forma Smith tiene una complejidad cúbica en el tamaño de la matriz involucrada, ya que utiliza operaciones de fila y columna, lo que lo hace inadecuado para complejos de celdas grandes. En segundo lugar, las matrices intermedias que resultan de la aplicación del algoritmo de la forma Smith se completan incluso si uno comienza y termina con matrices dispersas.

Algoritmos de forma normal de Smith eficientes y probabilísticos, como los que se encuentran en la biblioteca LinBox. Reducciones homotópicas simples para preprocesar 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 R TDAstats. En algunas aplicaciones, como en TDA, es útil tener representantes de clases de homología que sean lo más "pequeños" posible. Esto se conoce como el problema de la localización de 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. Preliminary version appeared at SODA 2010.Sin embargo, el entorno particular de aproximación de 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 Juego Único. .

Véase también

Geometría computacional Modelado geométrico

Referencias

Enlaces externos

Archivo de software CompuTop. Taller sobre la aplicación de la topología en la ciencia y la ingeniería. Topología computacional en la Universidad de Stanford Archivado. Software de homología computacional (CHomP) en la Universidad Rutgers. Software de homología computacional (RedHom) en la Universidad Jagellón Archivado. El proyecto de software Perseus para homología (persistente). El software de homología persistente javaPlex en Stanford. PHAT: caja de herramientas de algoritmos de homología persistente.

Libros

Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, .

Categoría:Campos de estudio computacionales Categoría:Ciencias de la computación Categoría:Complejidad computacional Categoría:Matemáticas aplicadas