Tarea de desacoplamiento
La tarea de desatar es la tarea de reconocimiento algorítmico de un nudo trivial si se da alguna representación del nudo, es decir, un diagrama de nudo . Hay varios tipos de algoritmos de desvinculación. El principal problema no resuelto es si el problema se puede resolver en tiempo polinomial , es decir, si el problema pertenece a la clase
de complejidad P.
Complejidad computacional
Los primeros pasos para definir la complejidad computacional se dieron para demostrar que el problema pertenece a clases de complejidad más complejas que contienen la clase P. Usando superficies normales para describir las superficies de Seifert de un nudo dado, Hass, Lagarias y Pippenger [1] demostraron que el problema de la desvinculación pertenece a la clase de complejidad NP . Hara, Tani y Yamamoto [2] afirmaron que la desvinculación pertenece a la clase AM ∩ co-AM . Posteriormente, sin embargo, retiraron su solicitud [3] . En 2011 , Greg Kuperberg demostró que (suponiendo que la hipótesis de Riemann generalizada sea cierta ) el problema de desvinculación pertenece a la clase co-NP [4] .
El problema de desvinculación tiene la misma complejidad computacional que verificar si una incrustación de un gráfico no dirigido en el espacio euclidiano está desvinculada [5] .
El nudo de Ochiai, que contiene 139 vértices, por ejemplo, se desató por primera vez usando una computadora en 108 horas, pero este tiempo se redujo posteriormente a 10 minutos [6]
Desvincular algoritmos
Algunos algoritmos para resolver el problema de desvinculación se basan en la teoría de Haken de superficies normales :
- El algoritmo de Haken usa la teoría de las superficies normales para encontrar un disco cuyo límite esté anudado. Haken usó originalmente este algoritmo para mostrar que el problema de desvinculación se puede resolver, pero no analizó la complejidad computacional del algoritmo en detalle.
- Hass, Lagarias y Pippenger demostraron que el conjunto de todas las superficies normales se puede representar como puntos enteros en un cono poliédrico , y que una superficie que indica la posibilidad de desvincular una curva (si la hay) 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 de borde y verificar si son límites de disco anudados. Hass, Lagarias y Pippenger usaron este método para demostrar que encontrar un desatado pertenece a la clase NP. Investigadores posteriores como Barton [7] mejoraron su análisis al mostrar que este algoritmo puede ser útil con complejidad exponencial de bajo orden (en función del número de intersecciones).
- El algoritmo de Birman y Hirsch [8] utiliza un haz trenzado , una estructura ligeramente diferente a la de una superficie normal. Sin embargo, para analizar su comportamiento volvieron a la teoría de las superficies normales.
Otros enfoques:
- El número de movimientos de Reidemeister necesarios para llevar el diagrama de nudo trivial a la forma estándar es, como mucho, polinomial en el número de intersecciones [9] . Por lo tanto, una búsqueda completa de todos los movimientos de Reidemeister puede detectar la trivialidad de un nudo en tiempo exponencial.
- De manera similar, dos triangularizaciones cualesquiera del mismo complemento de nodo pueden conectarse mediante una secuencia de movimientos de Pachner de una longitud no superior al doble de la exponencial del número de intersecciones [10] . Por lo tanto, uno puede determinar si un nudo es trivial al verificar secuencias de movimientos de Puchner de esa longitud, comenzando con el complemento de un nudo dado, y luego verificando si alguno de esos movimientos se puede convertir en una trianulación de toro completo estándar . El tiempo de este método debería ser tres veces exponencial, pero los experimentos muestran que estos límites son muy pesimistas y que se necesitan muchos menos movimientos de Pachner [11] .
- La finitud residual del grupo de nudos (que se deriva de la geometrización de las variedades de Haken ) da un algoritmo: verificamos si el grupo contiene un grupo de factores finitos no cíclicos. Esta idea se usa en la prueba de Kuperberg de que el problema de desvinculación pertenece a la clase co-NP.
- La homología de Floer de un nudo define el género de un nudo, que es 0 si y solo si el nudo es trivial. Se puede calcular una versión combinatoria de la homología de Floer de un nudo [12] .
- La homología de Khovanov define la trivialidad del nudo según los resultados de Cronheimer y Mrovka [13] . La complejidad de la homología de Khovanov es al menos la misma que la del problema #P-difícil de calcular el polinomio de Jones , pero se puede calcular utilizando el programa y el algoritmo de Bar-Nathan [14] . Bar-Nathan no brinda un análisis riguroso de su algoritmo, pero asume heurísticamente que el algoritmo es exponencial en el ancho de ruta del gráfico del diagrama de intersección, que, a su vez, es como máximo la raíz cuadrada del número de intersecciones (con algún factor ).
El estudio de la complejidad de estos algoritmos está en curso.
Véase también
Notas
- ↑ Hass, Lagarias, Pippenger, 1999 .
- ↑ Hara, Tani, Yamamoto, 2005 .
- ↑ Mencionado como "comunicación privada" [15] en la lista de citas del artículo de Kuperberg (Kuperberg, 2014).
- ↑ Kuperberg, 2014 .
- ↑ Kawarabayashi, Kreutzer, Mohar, 2010 .
- ↑ Ladd, Kavraki, 2004 .
- ↑ Burton, 2011a .
- ↑ Birman, Hirsch, 1998 .
- ↑ Lackenby, 2015 .
- ↑ Mijatovic, 2005 .
- ↑ Burton, 2011b .
- ↑ Manolescu, Ozsvath, Sarkar, 2009 .
- ↑ Kronheimer, Mrowka, 2011 .
- ↑ Bar-Natán, 2007 .
Literatura
- Dror Bar-Natan. Cálculos rápidos de homología de Khovanov // Revista de teoría de nudos y sus ramificaciones . - 2007. - T. 16 , núm. 3 . - S. 243-255 . -doi : 10.1142/ S0218216507005294 . - arXiv : matemáticas.GT/ 0606318 .
- Joan S. Birman, Michael Hirsch. Un nuevo algoritmo para reconocer el nudo // Geometría y topología . - 1998. - T. 2 . - S. 178-220 . -doi : 10.2140 / gt.1998.2.175 .
- Benjamín A. Burton. Caras admisibles máximas y límites asintóticos para el espacio de solución de superficie normal // Journal of Combinatorial Theory . — 2011a. - T. 118 , n. 4 . - S. 1410-1435 . -doi : 10.1016/ j.jcta.2010.12.011 . -arXiv : 1004.2605 . _
- Benjamín Burton. proc. 27º Simposio ACM sobre Geometría Computacional . — 2011b. - S. 153-162. -doi : 10.1145/ 1998196.1998220 .
- Wolfgang Haken. Theorie der Normalflächen // Acta Mathematica . - 1961. - T. 105 . - S. 245-375 . -doi : 10.1007 / BF02559591 .
- Masao Hara, Seiichi Tani, Makoto Yamamoto. proc. 16º Simposio ACM-SIAM sobre algoritmos discretos (SODA '05) . - 2005. - S. 359-364.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. La complejidad computacional de los problemas de nudos y enlaces // Journal of the ACM . - 1999. - T. 46 , núm. 2 . - S. 185-211 . -doi : 10.1145/ 301970.301971 . -arXiv : matemáticas / 9807016 .
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. El número de movimientos de Reidemeister necesarios para desanudar // Diario de la Sociedad Matemática Americana . - 2001. - T. 14 , núm. 2 . - S. 399-428 . -doi : 10.1090/ S0894-0347-01-00358-7 .
- Ken-ichi Kawarabayashi, Stephan Kreutzer, Bojan Mohar. proc. Simposio ACM sobre geometría computacional (SoCG '10) . - 2010. - S. 97-106. -doi : 10.1145/ 1810959.1810975 .
- Peter Kronheimer, Tomasz Mrowka. La homología de Khovanov es un detector de nudos // Publications Mathématiques de l'IHÉS . - 2011. - T. 113 , núm. 1 . - S. 97-208 . -doi : 10.1007 / s10240-010-0030-y . -arXiv : 1005.4346 . _
- Greg Kuperberg. El nudo está en NP, módulo GRH // Avances en Matemáticas . - 2014. - T. 256 . - S. 493-506 . -doi : 10.1016/ j.aim.2014.01.007 . -arXiv : 1112.0845 . _
- Marc Lackenby. Un límite superior polinomial en Reidemeister se mueve // Annals of Mathematics. - 2015. - T. 182 , núm. 2 . - S. 491-564 . doi : 10.4007 / annals.2015.182.2.3 . -arXiv : 1302.0180 . _
- Andrew M. Ladd, Lydia E. Kavraki. Fundamentos algorítmicos de la robótica V / Jean-Daniel Boissonnat, Joel Burdick, Ken Goldberg, Seth Hutchinson. - Springer, 2004. - T. 7. - S. 7-23. - (Tractos Springer en Robótica Avanzada). -doi : 10.1007 / 978-3-540-45058-0_2 .
- Ciprian Manolescu, Peter S. Ozsvath, Sucharit Sarkar. Una descripción combinatoria de la homología del nudo Floer // Annals of Mathematics . - 2009. - T. 169 , núm. 2 . - S. 633-660 . - doi : 10.4007/annals.2009.169.633 . — arXiv : matemáticas/0607691 .
- Aleksandar Mijatovic. Estructuras simples de complementos de nudos // Mathematical Research Letters. - 2005. - T. 12 , núm. 6 _ - S. 843-856 . -doi : 10.4310 / mrl.2005.v12.n6.a6 . — arXiv : matemáticas/0306117 .
Enlaces