Dos diagramas simples del nudoUn complicado diagrama de desanudado de Morwen Thistlethwaite
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.
Complejidad computacional
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.
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 grupos finitos no cíclicos. 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.
^ Mencionado como una "comunicación personal" en la referencia [15] de Kuperberg (2014).
^ Kuperberg (2014)
^ Lackenby (2021)
^ "Marc Lackenby anuncia un nuevo algoritmo de reconocimiento de nudos que se ejecuta en tiempo cuasi-polinomial". Instituto Matemático de la Universidad de Oxford . Consultado el 21 de mayo de 2024 .
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 en arco de enlaces: simplificación monótona", Fundamenta Mathematicae , 190 : 29–76, arXiv : math/0208153 , doi : 10.4064/fm190-0-3, S2CID 14137437.
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.
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
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.
