Topología computacional

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.[1]​[2]​[3]​

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. [4]​ Saul Schleimer continuó demostrando que el problema radica en la clase de complejidad NP. [5]​ Además, Raphael Zentner demostró que el problema reside en la clase de complejidad coNP, [6]​ 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 [7]​ 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 [8]​ 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.[9]​

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,[10]​ 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.[11]​ 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. [12]​
• 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 [13]​ así como también en las co-NP. [14]​ Se sabe que el problema de determinar el género de un nudo tiene la clase de complejidad PSPACE. [13]​

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, [15]​ 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. [16]​
• 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. [17]​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. [18]​

Véase también

• Geometría computacional
• Modelado geométrico

Referencias

1. Blevins, Ann Sizemore; Bassett, Danielle S. (2020), «Topology in Biology», en Sriraman, Bharath, ed., Handbook of the Mathematics of the Arts and Sciences (en inglés) (Cham: Springer International Publishing): 1-23, ISBN 978-3-319-70658-0, doi:10.1007/978-3-319-70658-0_87-1 .
2. Chiou, Lyndie (26 March 2024). «Topologists Tackle the Trouble With Poll Placement». Quanta Magazine. Consultado el 1 April 2024. 
3. Zomorodian, Afra J. (10 de enero de 2005). Topology for Computing (en inglés). Cambridge University Press. ISBN 978-1-139-44263-3. Consultado el 27 de enero de 2025. 
4. Burton, Benjamin A. (2004). «Introducing Regina, the 3-manifold topology software». Experimental Mathematics 13 (3): 267-272. doi:10.1080/10586458.2004.10504538. 
5. Schleimer, Saul (2011). «Sphere Recognition Lies in NP». 
6. Zentner, Raphael (2018). «Integer homology 3-spheres admit irreducible representations in SL(2,C)». Duke Mathematical Journal 167 (9): 1643-1712. arXiv:1605.08530. doi:10.1215/00127094-2018-0004. 
7. Kuperberg, Greg (2014). «Knottedness is in NP, modulo GRH». Advances in Mathematics 256: 493-506. arXiv:1112.0845. doi:10.1016/j.aim.2014.01.007. 
8. Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). «The Weber-Seifert dodecahedral space is non-Haken». Transactions of the American Mathematical Society 364 (2): 911-932. arXiv:0909.4625. doi:10.1090/S0002-9947-2011-05419-X. 
9. Manning, Jason (23 de enero de 2002), Algorithmic detection and description of hyperbolic structures on closed 3-manifolds with solvable word problem, doi:10.48550/arXiv.math/0102154, consultado el 27 de enero de 2025 .
10. Matveev, Sergei (2003). «Algorithmic Topology and Classification of 3-Manifolds». Algorithms and Computation in Mathematics (en inglés). ISSN 1431-1550. doi:10.1007/978-3-662-05102-3. Consultado el 27 de enero de 2025. 
11. Kuperberg, Greg (2019). «Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization». Pacific Journal of Mathematics 301: 189-241. arXiv:1508.06720. doi:10.2140/pjm.2019.301.189. 
12. Costantino, Francesco; Thurston, Dylan (2008). «3-manifolds efficiently bound 4-manifolds». Journal of Topology 1 (3): 703-745. arXiv:math/0506577. doi:10.1112/jtopol/jtn017. 
13. Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas (1999), «The computational complexity of knot and link problems», Journal of the ACM 46 (2): 185-211, doi:10.1145/301970.301971 .
14. Lackenby, Marc (2021), «The efficient certification of Knottedness and Thurston norm», Advances in Mathematics 387: 107796, doi:10.1016/j.aim.2021.107796 .
15. Brown, Edgar H. (1957), «Finite Computability of Postnikov Complexes», Annals of Mathematics (2) 65 (1): 1-20, doi:10.2307/1969664 .
16. Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). «TDAstats: R pipeline for computing persistent homology in topological data analysis». Journal of Open Source Software 3 (28): 860. Bibcode:2018JOSS....3..860R. PMC 7771879. PMID 33381678. doi:10.21105/joss.00860. 
17. Chen, Chao; Freedman, Daniel (2011). «Hardness results for homology localization». Discrete & Computational Geometry 45 (3): 425-448. doi:10.1007/s00454-010-9322-8.  Preliminary version appeared at SODA 2010.
18. . 34th Internat. Symp. Comput. Geom. (SoCG) '18. 2018. doi:10.4230/LIPIcs.SoCG.2018.43. .

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

• Tomasz Kaczynski; Konstantin Mischaikow; Marian Mrozek (2004). Computational Homology. Springer. ISBN 0-387-40853-3. 
• Afra J. Zomorodian (2005). Topology for Computing. Cambridge. ISBN 0-521-83666-2. 
• Computational Topology: An Introduction, Herbert Edelsbrunner, John L. Harer, AMS Bookstore, 2010, ISBN 978-0-8218-4925-5.

• Datos: Q4129926