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 3-esferas de Rubinstein y Thompson . Este es un algoritmo que toma como entrada una 3-variedad triangulada y determina si la variedad es homeomorfa o no a la 3-esfera . Tiene un tiempo de ejecución exponencial en el número de símplex tetraédricos en la 3-variedad 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 radica en la clase de complejidad coNP, ^[6] siempre que se cumpla la hipótesis generalizada de Riemann. Utiliza la teoría de calibre instantón, el teorema de geometrización de 3-variedades y el trabajo posterior de Greg Kuperberg ^[7] sobre la complejidad de la detección de anudamientos.
• La descomposición de suma-conexión 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 variedad 3 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]

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

Algoritmos de conversión

• SnapPea implementa un algoritmo para convertir un diagrama de nudos o enlaces planos en una triangulación cuspide. Este algoritmo tiene un tiempo de ejecución aproximadamente lineal en cuanto al número de cruces en el diagrama y un perfil de memoria bajo. El algoritmo es similar al algoritmo de Wirthinger para construir presentaciones del grupo fundamental de complementos de enlaces dados por diagramas planos. De manera similar, SnapPea puede convertir presentaciones quirúrgicas de 3-variedades en triangulaciones de la 3-variedad presentada.
• D. Thurston y F. Costantino tienen un procedimiento para construir una variedad triangulada de 4 dimensiones a partir de una variedad triangulada de 3 dimensiones. De manera similar, se puede utilizar para construir presentaciones quirúrgicas de variedades trianguladas de 3 dimensiones, 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 la variedad triangulada dada. ^[12]
• S. Schleimer tiene un algoritmo que produce una variedad triangulada, dada como entrada una palabra (en generadores de torsión de Dehn ) para el grupo de clases de mapeo de una superficie. La variedad triangulada es la que utiliza la palabra como el mapa adjunto para una división de Heegaard de la variedad triangulada. 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]
• Existen algoritmos de tiempo polinomial para el cálculo del polinomio de Alexander de un nudo. ^[15]
• El polinomio de Jones , el polinomio HOMFLY y los invariantes de Reshetikhin–Turaev son tracktable de parámetros fijos , mientras que también se sabe que el polinomio de Jones es #P-hard . ^[16] El cálculo del primer coeficiente del polinomio HOMFLYPT y de Kauffman está en P. ^[17]
• La aproximación aditiva del polinomio de Jones es BQP-completa , es decir, equivalentemente difícil que los algoritmos cuánticos de tiempo polinomial. ^[18]
• Dados dos nudos (domesticados) mediante diagramas de enlace, decidir si son equivalentes es ER . Esto se establece reduciendo la equivalencia de nudos ( isotopía ) a la equivalencia ( homeomorfía ) de los complementos de nudos asociados que son 3-variedades que a su vez pueden codificarse mediante triangulaciones . Dado que estos complementos de nudos son variedades de Haken , se utiliza un resultado de que el problema de equivalencia de estas variedades está en ER. No parece haber una buena referencia para esto, estos resultados están dispersos en la literatura en el campo, pero son bien conocidos por la comunidad.

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 , ^[19] 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 de contorno 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 principales. En primer lugar, el algoritmo básico de la forma de 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 celulares grandes. En segundo lugar, las matrices intermedias que resultan de la aplicación del algoritmo de la forma de 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. ^[20]

Véase también

• Topología computable (el estudio de la naturaleza topológica del cálculo)
• Geometría computacional
• Topología digital
• Análisis de datos topológicos
• Razonamiento espacio-temporal
• Matemáticas experimentales
• Modelado geométrico

Referencias

1. Afra J. Zomorodian, Topología para computación, Cambridge, 2005, xi
2. Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topología en biología", Manual de matemáticas de las artes y las ciencias , Cham: Springer International Publishing, págs. 1–23, doi :10.1007/978-3-319-70658-0_87-1, ISBN 978-3-319-70658-0, Número de identificación del sujeto  226695484
3. Chiou, Lyndie (26 de marzo de 2024). "Los topólogos abordan el problema de la ubicación de las encuestas". Quanta Magazine . Consultado el 1 de abril de 2024 .
4. Burton, Benjamin A. (2004). "Introducción a Regina, el software de topología de 3 variedades" (PDF) . Experimental Mathematics . 13 (3): 267–272. doi :10.1080/10586458.2004.10504538. S2CID  16566807.
5. Schleimer, Saul (2011). "El reconocimiento de esferas reside en la NP" (PDF) – vía University of Warwick .
6. Zentner, Raphael (2018). "Las 3-esferas de homología de enteros admiten representaciones irreducibles en SL(2,C)". Duke Mathematical Journal . 167 (9): 1643–1712. arXiv : 1605.08530 . doi :10.1215/00127094-2018-0004. S2CID  119275434.
7. Kuperberg, Greg (2014). "La anudación está en NP, módulo GRH". Avances en Matemáticas . 256 : 493–506. arXiv : 1112.0845 . doi : 10.1016/j.aim.2014.01.007 . S2CID  12634367.
8. Burton, Benjamin A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). "El espacio dodecaédrico de Weber-Seifert no es Haken". Transacciones de la American Mathematical Society . 364 (2): 911–932. arXiv : 0909.4625 . doi :10.1090/S0002-9947-2011-05419-X. S2CID  18435885.
9. J. Manning, Detección algorítmica y descripción de estructuras hiperbólicas en 3-variedades con problema verbal solucionable, Geometry and Topology 6 (2002) 1–26
10. S. Matveev, Topología algorítmica y clasificación de 3-variedades, Springer-Verlag 2003
11. Kuperberg, Greg (2019). "Homeomorfismo algorítmico de 3-variedades como corolario de la geometrización". Revista del Pacífico de Matemáticas . 301 : 189–241. arXiv : 1508.06720 . doi :10.2140/pjm.2019.301.189. S2CID  119298413.
12. Costantino, Francesco; Thurston, Dylan (2008). "Variedades de 3 a 4 están ligadas de manera eficiente". Journal of Topology . 1 (3): 703–745. arXiv : math/0506577 . doi :10.1112/jtopol/jtn017. S2CID  15119190.
13. Hass, Joel ; Lagarias, Jeffrey C. ; Pippenger, Nicholas (1999), "La complejidad computacional de los problemas de nudos y enlaces", Journal of the ACM , 46 (2): 185–211, arXiv : math/9807016 , doi :10.1145/301970.301971, S2CID  125854
14. Lackenby, Marc (2021), "La certificación eficiente de la anudación y la norma de Thurston", Advances in Mathematics , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796, S2CID  119307517
15. "Página principal", El Atlas de Nudos .
16. Maria, Clément (2019). "Complejidad parametrizada de invariantes cuánticos". arXiv : 1910.00477 [math.GT].
17. Przytycki, Jozef H. (2017). "El primer coeficiente de los polinomios de Homflypt y Kauffman: prueba de Vertigan de la complejidad polinómica mediante programación dinámica". arXiv : 1707.07733 [math.GT].
18. Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "Un algoritmo cuántico polinomial para aproximar el polinomio de Jones". arXiv : quant-ph/0511096 .
19. Brown, Edgar H. (1957), "Computabilidad finita de complejos de Postnikov", Anales de Matemáticas (2) , 65 (1): 1–20, doi :10.2307/1969664, JSTOR  1969664
20. Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018). "TDAstats: canalización R para calcular homología persistente en análisis de datos topológicos". Journal of Open Source Software . 3 (28): 860. Bibcode :2018JOSS....3..860R. doi : 10.21105/joss.00860 . PMC 7771879 . PMID  33381678. 

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 el 22 de junio de 2007 en Wayback Machine
• Software de homología computacional (CHomP) en la Universidad Rutgers.
• Software de homología computacional (RedHom) en la Universidad Jagellón Archivado el 15 de julio de 2013 en Wayback Machine .
• 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 Mrožek (2004). Homología computacional. Saltador. ISBN 0-387-40853-3.
• Afra J. Zomorodian (2005). Topología para la computación. Cambridge. ISBN 0-521-83666-2.
• Topología computacional: una introducción, Herbert Edelsbrunner, John L. Harer, Librería AMS, 2010, ISBN 978-0-8218-4925-5