stringtranslate.com

Problema de desenredado

Problema sin resolver en matemáticas :
¿Es posible reconocer nudos en tiempo polinomial?
Dos diagramas simples del nudo
Un 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.

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]

Algoritmos de desenredado

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

Otros enfoques incluyen:

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

Véase también

Notas

  1. ^ Mencionado como una "comunicación personal" en la referencia [15] de Kuperberg (2014).
  2. ^ Kuperberg (2014)
  3. ^ Lackenby (2021)
  4. ^ "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 .
  5. ^ Kawarabayashi, Kreutzer y Mohar (2010).
  6. ^ Lackenby (2015).
  7. ^ Mijatović (2005).
  8. ^ Burton (2011b).
  9. ^ Dynnikov (2006).
  10. ^ Kronheimer y Mrowka (2011)

Referencias