¿Qué parte queda sin resolver en el problema Unknotting? (después de los resultados de Bar-Natan, Khovanov, Kronheimer y Mrowka)

Question

• Kronheimer y Mrowka mostró que el Khovanov homología detecta la unknot.
• Bar-Natan mostró un programa para calcular el Khovanov homología rápido: no hubo un riguroso análisis de la complejidad del algoritmo, pero se estima por Bar-Natan que el algoritmo se ejecuta en un tiempo proporcional a la raíz cuadrada del número de cruces, por lo que es menos lineal en el número de cruces.

Lo que yo podría entender de esto, es que si tenemos:

1. una prueba de la exactitud de Bar-Natan del algoritmo

2. un riguroso análisis de algoritmo que muestra el tiempo de ejecución del algoritmo es polinomial o menos

a continuación, tenemos una prueba de que la unknotting problema está en P.

Supongo que este no es realmente el caso.

Es lo que yo asumo aquí verdad? si no, ¿por qué? (quizá Bar-Natan del algoritmo no determinista?)

Answer 1

Para fortalecer Sam Nead la respuesta, tenga en cuenta que es trivial para calcular el polinomio de Jones de la Khovanov de homología. Es conocido que la computación (o incluso la aproximación) el polinomio de Jones es #P-duro:

• Kuperberg, Greg, ¿qué tan difícil es para aproximar el polinomio de Jones?, La Teoría De La Comput. 11 (2015), 183-219. http://arxiv.org/pdf/0908.0512.pdf

• Vertigan, Dirk, La complejidad computacional de Tutte invariantes para grafos planares, SIAM J. Comput. 35 (2005), no. 3, 690-712.

Por lo tanto, cualquier enfoque a lo largo de estas líneas definitivamente no darle un algoritmo eficiente para la detección de la unknot (suponiendo que la complejidad estándar-teoría de las conjeturas).

Tenga en cuenta que Jones conjeturó que el polinomio de Jones en sí detecta la unknot, pero por supuesto que todavía no le dan un algoritmo eficiente.

Answer 2

Una rápida ojeada del documento al que se vinculó encuentra los comentarios (en el párrafo dos de la página dos) de Bar-Natan que sugieren que su mejora debería llevar tiempo$\exp({\sqrt{n}})$, superando el algoritmo ingenuo (tomando tiempo$\exp(n)$). Es decir, la mejora con suerte hace que un algoritmo exponencial sea subexponencial. No está reclamando un algoritmo sublineal.

Answer 3

Esto no es directamente lo que le pides, pero también vale la pena señalar que unknot detección es $\text{NP} \cap \text{co-NP}$, es decir, hay polinomio-seleccionable certificados que demuestran que un nudo es el unknot o que el nudo no es el unknot. El $\text{NP}$ certificado usos normales de la superficie de la teoría:

• Ian Agol, Joel Hass, William Thurston, La complejidad computacional de nudo de género y que abarca la zona. Trans. Amer. De matemáticas. Soc. 358 (2006), no. 9, 3821-3850.

El $\text{co-NP}$ certificado es actualmente condicional en la generalización de la Hipótesis de Riemann, y se basa en la búsqueda de representaciones del nudo de grupo:

• Greg Kuperberg, Knottedness está en NP, modulo GRH. Adv. De Matemáticas. 256 (2014), 493-506.

(No debería ser otra prueba de la $\text{co-NP}$ resultado del uso normal de la superficie de la teoría y de la noción de jerarquías. Ian Agol esbozado que hace algún tiempo, pero los detalles son difíciles.)

La clase $\text{NP} \cap \text{co-NP}$ es relativamente pequeña, y esto da razones para creer que la detección de la unknot es en $\text{P}$.

(Yo habría hecho este comentario, pero creo que es demasiado tiempo para eso.)