Problema de desenredado

En matemáticas , el problema de desanudación es el problema de reconocer algorítmicamente el desanudado , dada alguna representación de un nudo, por ejemplo, un diagrama de nudos . Existen varios tipos de algoritmos de desanudación. Un desafío importante sin resolver es determinar si el problema admite un algoritmo de tiempo polinomial ; es decir, si el problema se encuentra en la clase de complejidad P.

Los primeros pasos para determinar la complejidad computacional se dieron al probar que el problema está en clases de complejidad mayores, que contienen la clase P. Al usar superficies normales para describir las superficies de Seifert de un nudo dado, Hass, Lagarias y Pippenger (1999) demostraron que el problema de desanudamiento está en la clase de complejidad NP . Hara, Tani y Yamamoto (2005) afirmaron el resultado más débil de que el desanudamiento está en AM ∩ co-AM ; sin embargo, más tarde se retractaron de esta afirmación. ^[1] En 2011, Greg Kuperberg demostró que (asumiendo la hipótesis generalizada de Riemann ) el problema de desanudamiento está en co-NP , ^[2] y en 2016, Marc Lackenby proporcionó una prueba incondicional de membresía co-NP. ^[3]

En 2021, Lackenby anunció un algoritmo de reconocimiento de nudos que, según él, se ejecutaba en tiempo cuasipolinomial . ^[4] Hasta mayo de 2024, el resultado no se ha publicado en la literatura revisada por pares.

El problema de desanudamiento tiene la misma complejidad computacional que probar si una incrustación de un gráfico no dirigido en el espacio euclidiano no tiene vínculos . ^[5]

Varios algoritmos que resuelven el problema del desanudamiento se basan en la teoría de superficies normales de Haken :

• El algoritmo de Haken utiliza la teoría de superficies normales para encontrar un disco cuyo límite es el nudo. Haken utilizó originalmente este algoritmo para demostrar que el desanudamiento es decidible, pero no analizó su complejidad con más detalle.
• Hass, Lagarias y Pippenger demostraron que el conjunto de todas las superficies normales puede representarse por los puntos enteros en un cono poliédrico y que una superficie que atestigua la falta de nudos de una curva (si existe) siempre se puede encontrar en uno de los rayos extremos de este cono. Por lo tanto, los métodos de enumeración de vértices se pueden utilizar para enumerar todos los rayos extremos y comprobar si alguno de ellos corresponde a un disco delimitador del nudo. Hass, Lagarias y Pippenger utilizaron este método para demostrar que la falta de nudos está en NP; investigadores posteriores como Burton (2011a) refinaron su análisis, demostrando que este algoritmo puede ser útil (aunque no en tiempo polinomial), siendo su complejidad una función exponencial simple de orden bajo del número de cruces.
• El algoritmo de Birman & Hirsch (1998) utiliza foliaciones trenzadas, un tipo de estructura algo diferente a una superficie normal. Sin embargo, para analizar su comportamiento recurren a la teoría de superficies normales.

Otros enfoques incluyen:

• La cantidad de movimientos de Reidemeister necesarios para cambiar un diagrama de desanudado al diagrama de desanudado estándar es, como máximo, polinomial en la cantidad de cruces. ^[6] Por lo tanto, una búsqueda de fuerza bruta para todas las secuencias de movimientos de Reidemeister puede detectar desanudamientos en tiempo exponencial.
• De manera similar, dos triangulaciones cualesquiera del mismo complemento de nudo pueden estar conectadas por una secuencia de movimientos de Pachner de longitud como máximo doblemente exponencial en el número de cruces. ^[7] Por lo tanto, es posible determinar si un nudo es el desnudo probando todas las secuencias de movimientos de Pachner de esta longitud, comenzando por el complemento del nudo dado, y determinando si alguna de ellas transforma el complemento en una triangulación estándar de un toro sólido . El tiempo para este método sería triplemente exponencial; sin embargo, la evidencia experimental sugiere que este límite es muy pesimista y que se necesitan muchos menos movimientos de Pachner. ^[8]
• Cualquier presentación de arco de un nudo no resuelto se puede simplificar monótonamente a una mínima usando movimientos elementales. ^[9] Por lo tanto, una búsqueda de fuerza bruta entre todas las presentaciones de arco de complejidad no mayor proporciona un algoritmo exponencial único para el problema de desanudación.
• La finitud residual del grupo de nudos (que se desprende de la geometrización de las variedades de Haken ) da un algoritmo: comprobar si el grupo tiene un cociente de grupo finito no cíclico. Esta idea se utiliza en el resultado de Kuperberg de que el problema de desanudación está en co-NP.
• La homología de Floer del nudo detecta el género del nudo, que es 0 si y solo si el nudo es un nudo no determinado. Una versión combinatoria de la homología de Floer del nudo permite calcularlo (Manolescu, Ozsváth y Sarkar 2009).
• La homología de Khovanov detecta el nudo de acuerdo con un resultado de Kronheimer y Mrowka . ^[10] La complejidad de la homología de Khovanov es al menos tan alta como el problema #P-hard de calcular el polinomio de Jones , pero se puede calcular en la práctica utilizando un algoritmo y programa de Bar-Natan (2007). Bar-Natan no proporciona un análisis riguroso de su algoritmo, pero estima heurísticamente que es exponencial en el ancho de ruta de un diagrama de cruces, que a su vez es como máximo proporcional a la raíz cuadrada del número de cruces.

Comprender la complejidad de estos algoritmos es un campo de estudio activo.

• Topología algorítmica
• Número de desenredado

• Bar-Natan, Dror (2007), "Cálculos rápidos de homología de Khovanov", Journal of Knot Theory and Its Ramifications , 16 (3): 243–255, arXiv : math.GT/0606318 , doi :10.1142/S0218216507005294, MR  2320156, S2CID  17036344.
• Birman, Joan S. ; Hirsch, Michael (1998), "Un nuevo algoritmo para reconocer nudos no definidos", Geometry and Topology , 2 : 178–220, arXiv : math/9801126 , doi :10.2140/gt.1998.2.175, S2CID  17776505.
• Burton, Benjamin A. (2011a), "Caras máximas admisibles y límites asintóticos para el espacio de soluciones de superficies normales" (PDF) , Journal of Combinatorial Theory , Serie A, 118 (4): 1410–1435, arXiv : 1004.2605 , doi :10.1016/j.jcta.2010.12.011, MR  2763065, S2CID  11461722.
• Burton, Benjamin (2011b), "El gráfico de Pachner y la simplificación de triangulaciones de 3 esferas", Proc. 27.° Simposio ACM sobre geometría computacional, págs. 153-162, arXiv : 1011.4169 , doi : 10.1145/1998196.1998220, S2CID  382685.
• Dynnikov, Ivan (2006), "Presentaciones de arcos de enlaces: simplificación monótona", Fundamenta Mathematicae , 190 : 29–76, arXiv : math/0208153 , doi :10.4064/fm190-0-3, S2CID  14137437.
• Haken, Wolfgang (1961), "Theorie der Normalflächen", Acta Mathematica , 105 : 245–375, doi : 10.1007/BF02559591.
• Hara, Masao; Tani, Seiichi; Yamamoto, Makoto (2005), "El desenlace está en AM ∩ co-AM", Actas del 16.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '05), págs. 359–364.
• 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, MR  1693203, S2CID  125854.
• Hass, Joel ; Lagarias, Jeffrey C. (2001), "El número de movimientos de Reidemeister necesarios para desanudar", Journal of the American Mathematical Society , 14 (2): 399–428, arXiv : math/9807012 , doi :10.1090/S0894-0347-01-00358-7, MR  1815217, S2CID  15654705.
• Kawarabayashi, Ken-ichi ; Kreutzer, Stephan; Mohar, Bojan (2010), "Incrustaciones planas y sin enlaces en el espacio tridimensional y el problema del nudo" (PDF) , Proc. ACM Symposium on Computational Geometry (SoCG '10) , págs. 97–106, doi :10.1145/1810959.1810975, S2CID  12290801.
• Kronheimer, Peter; Mrowka, Tomasz (2011), "La homología de Khovanov es un detector de nudos", Publications Mathématiques de l'IHÉS , 113 (1): 97–208, arXiv : 1005.4346 , doi :10.1007/s10240-010-0030-y, S2CID  119586228
• Kuperberg, Greg (2014), "La anudación está en NP, módulo GRH", Advances in Mathematics , 256 : 493–506, arXiv : 1112.0845 , doi : 10.1016/j.aim.2014.01.007, MR  3177300, S2CID  12634367.
• Lackenby, Marc (2015), "Un límite superior polinomial en movimientos de Reidemeister", Annals of Mathematics , Segunda serie, 182 (2): 491–564, arXiv : 1302.0180 , doi :10.4007/annals.2015.182.2.3, MR  3418524, S2CID  119662237.
• Lackenby, Marc (2021), "La certificación eficiente de la anudamiento y la norma de Thurston", Advances in Mathematics , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796, S2CID  119307517.
• Manolescu, Ciprian ; Ozsváth, Peter S. ; Sarkar, Sucharit (2009), "Una descripción combinatoria de la homología de nudos de Floer", Annals of Mathematics , Segunda serie, 169 (2): 633–660, arXiv : math/0607691 , Bibcode :2006math......7691M, doi :10.4007/annals.2009.169.633, MR  2480614, S2CID  15427272.
• Mijatović, Aleksandar (2005), "Estructuras simples de complementos de nudos", Mathematical Research Letters , 12 (6): 843–856, arXiv : math/0306117 , doi :10.4310/mrl.2005.v12.n6.a6, MR  2189244, S2CID  7726354