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 indica, es desarrollar algoritmos eficientes para resolver problemas que surgen naturalmente en campos como la geometría computacional , los gráficos , la robótica , la biología estructural y la química , utilizando métodos de topología computable . ^{[1] [2]}

Principales algoritmos por área temática

Teoría algorítmica de 3 variedades

Una gran familia de algoritmos relacionados con 3 variedades gira en torno a la teoría de superficies normales , que es una frase que abarca 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 variedad triangulada de 3 y determina si la variedad es homeomorfa a la de 3 esferas . 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 . ^[3] Saul Schleimer pasó a demostrar que el problema radica en la clase de complejidad NP . ^[4] Además, Raphael Zentner demostró que el problema radica en la clase de complejidad coNP, ^[5] siempre que se cumpla la hipótesis generalizada de Riemann. Utiliza la teoría del calibre instantáneo, 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 conectada de 3 variedades también se implementa 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 [7]} implementaron algorítmicamente la determinación de que la variedad 3 de Seifert-Weber no contiene ninguna superficie incompresible y se basó 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 . ^[8]

En la actualidad, la descomposición JSJ no se ha implementado algorítmicamente en software informático. Tampoco la descomposición del cuerpo comprimido. Existen algunas heurísticas muy populares y exitosas, como SnapPea , que tiene mucho éxito al calcular estructuras hiperbólicas aproximadas en 3 variedades trianguladas. Se sabe que la clasificación completa de 3 variedades se puede realizar algorítmicamente; ^[9] 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. . ^[10] Esto generaliza el resultado en el reconocimiento de 3 esferas.

Algoritmos de conversión

• SnapPea implementa un algoritmo para convertir un nudo plano o un diagrama de enlaces en una triangulación en cúspide. 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 presentaciones del grupo fundamental de complementos de enlace dados por diagramas planos. 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 debe tener un tiempo de ejecución polinómico en el número de tetraedros de la triangulación de 3 variedades dada. ^[11]
• S. Schleimer tiene un algoritmo que produce una variedad triple triangulada, dada la entrada de una palabra (en los generadores de torsión Dehn ) para el grupo de clases de mapeo de una superficie. La variedad 3 es la que usa la palabra como mapa adjunto para una división Heegaard de la variedad 3. El algoritmo se basa en el concepto de triangulación por capas .

Teoría de nudos algorítmicos

• Se sabe que determinar si un nudo es trivial o no se encuentra en las clases de complejidad NP ^[12] y co-NP . ^[13]
• Se sabe que el problema de determinar el género de un nudo tiene la clase de complejidad PSPACE . ^[12]
• Existen algoritmos de tiempo polinómico para el cálculo del polinomio de Alexander de un nudo. ^[14]
• 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 . ^[15] Calcular el primer coeficiente del polinomio HOMFLYPT y Kauffman está en P. ^[dieciséis]
• La aproximación aditiva del polinomio de Jones es BQP-completa , es decir, equivalentemente difícil como los algoritmos cuánticos de tiempo polinomial. ^[17]
• Dados dos nudos (domésticos) mediante diagramas de enlaces, decidir si son equivalentes es ER . Esto se establece reduciendo la equivalencia de nudos ( isotopía ) a la equivalencia ( homeomorfia ) 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 el 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 esferas de homotopía ".
• Métodos computacionales para la resolución de sistemas de ecuaciones polinómicas .
• Brown tiene un algoritmo para calcular los grupos de homotopía de espacios que son complejos finitos de Postnikov , ^[18] aunque no se considera implementable en general.

Homología computacional

El cálculo de los grupos de homología de complejos celulares se reduce a llevar las matrices límite a la forma normal de Smith . Aunque este es un problema algorítmicamente completamente resuelto, existen varios obstáculos técnicos para el cálculo eficiente de grandes complejos. Hay dos obstáculos centrales. En primer lugar, el algoritmo básico de la forma de Smith tiene complejidad cúbica en el tamaño de la matriz involucrada, ya que utiliza operaciones de filas y columnas, 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 de Smith se completan incluso si se 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 cálculos de homología de preprocesamiento, como en el paquete de software Perseus.
• Algoritmos para calcular la homología persistente de complejos filtrados , como en el paquete TDAstats R. ^[19]

Ver también

• Topología computable (el estudio de la naturaleza topológica de la computación)
• 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 de la informática, 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 a 23, doi :10.1007/978 -3-319-70658-0_87-1, ISBN 978-3-319-70658-0, S2CID  226695484
3. Burton, Benjamín A. (2004). "Presentamos Regina, el software de topología de tres colectores" (PDF) . Matemáticas Experimentales . 13 (3): 267–272. doi :10.1080/10586458.2004.10504538. S2CID  16566807.
4. Schleimer, Saúl (2011). "El reconocimiento de esferas reside en NP" (PDF) - a través de la Universidad de Warwick .
5. Zentner, Rafael (2018). "Las 3 esferas de homología de enteros admiten representaciones irreducibles en SL (2, C)". Revista de Matemáticas de Duke . 167 (9): 1643-1712. arXiv : 1605.08530 . doi :10.1215/00127094-2018-0004. S2CID  119275434.
6. Kuperberg, Greg (2014). "El nudo 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.
7. Burton, Benjamín A.; Hyam Rubinstein, J.; Tillmann, Stephan (2009). "El espacio dodecaédrico de Weber-Seifert no es de Haken". Transacciones de la Sociedad Matemática Estadounidense . 364 (2): 911–932. arXiv : 0909.4625 . doi :10.1090/S0002-9947-2011-05419-X. S2CID  18435885.
8. J.Manning, Detección algorítmica y descripción de estructuras hiperbólicas en 3 variedades con problemas verbales que se pueden resolver, Geometría y topología 6 (2002) 1–26
9. S.Matveev, Topología algorítmica y clasificación de 3 variedades, Springer-Verlag 2003
10. Kuperberg, Greg (2019). "Homeomorfismo algorítmico de 3 variedades como corolario de la geometrización". Revista Pacífico de Matemáticas . 301 : 189–241. arXiv : 1508.06720 . doi :10.2140/pjm.2019.301.189. S2CID  119298413.
11. Costantino, Francisco; Thurston, Dylan (2008). "3 colectores unidos eficientemente a 4 colectores". Revista de topología . 1 (3): 703–745. arXiv : matemáticas/0506577 . doi :10.1112/jtopol/jtn017. S2CID  15119190.
12. 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
13. Lackenby, Marc (2021), "La certificación eficiente de Knottedness y la norma Thurston", Avances en Matemáticas , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796, S2CID  119307517
14. "Página_principal", El atlas de nudos .
15. María, Clément (2019). "Complejidad parametrizada de invariantes cuánticos". arXiv : 1910.00477 [matemáticas.GT].
16. 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 [matemáticas.GT].
17. Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "Un algoritmo cuántico polinómico para aproximar el polinomio de Jones". arXiv : quant-ph/0511096 .
18. Brown, Edgar H. (1957), "Computabilidad finita de los complejos de Postnikov", Annals of Mathematics (2) , 65 (1): 1–20, doi :10.2307/1969664, JSTOR  1969664
19. Wadhwa, Raoul; Williamson, dibujó; Dhawan, Andrés; Scott, Jacob (2018). "TDAstats: canal R para calcular la homología persistente en el análisis de datos topológicos". Revista de software de código abierto . 3 (28): 860. Código bibliográfico : 2018JOSS....3..860R. doi : 10.21105/joss.00860 . PMC 7771879 . PMID  33381678. 

enlaces externos

• Archivo de software CompuTop
• Taller sobre Aplicación de la Topología en Ciencias e Ingeniería
• Topología computacional en la Universidad de Stanford Archivado el 22 de junio de 2007 en la Wayback Machine.
• Software de homología computacional (CHomP) en la Universidad de Rutgers.
• Software de homología computacional (RedHom) en la Universidad Jagellonian Archivado el 15 de julio de 2013 en Wayback Machine .
• El proyecto de software Perseus para la 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