Con la geometrización, el algoritmo de reconocimiento de 3 esferas de Rubinstein y el algoritmo de Manning, la teoría de los 3-manifolds ha alcanzado una cierta madurez en la que se pueden responder "fácilmente" muchas preguntas sobre los 3-manifolds, los nudos y los enlaces. Me gustaría tener un wiki de la comunidad donde colectivamente construyéramos un conocimiento de cuánto se sabe algorítmicamente, y lo "caro" que es saber algo, en el sentido de límites superiores de tiempo de ejecución, y límites superiores de uso de memoria (si están disponibles). En el peor de los casos, me gustaría saber que "no se conoce ningún algoritmo".
Espero dar forma al debate de esta manera: En esta entrada inicial se enumerarán las "cosas que queremos saber", y en las respuestas se elegirá uno de estos temas y se aportarán detalles. Cualquier detalle que conozcas, con referencias y ejemplos de implementación (si están disponibles). Preferencia por algoritmos que imagines que son realmente implementables, es decir, aquellos con estimaciones razonables de tiempo de ejecución, consumo razonable de memoria y que supongan datos de arranque razonables, algo que puedas dar a un ordenador sin demasiado dolor. A medida que se responda a los temas del primer post, se borrarán del primer post para mantener el desorden bajo.
Así que si hay cosas que quieres saber -- por ejemplo, ¿hay una estimación de cuánto tiempo se tardaría en calcular (?triangulaciones?) de todos los 3manifolds hiperbólicos completos de volumen finito que tienen el n-ésimo mayor volumen (entre los volúmenes de todos los manifolds de volumen finito), donde n es el ordinal de entrada? -- añada su pregunta al mensaje superior.
Por supuesto, lo único que busco son límites superiores en los tiempos de ejecución. Si conoces la clase de complejidad a la primera, genial. El sesgo es más hacia tiempos de ejecución reales de algoritmos que considerarías usar.
Permítanme que me ponga manos a la obra. Conozco las respuestas a algunas de ellas, e intentaré ponerme con algunas en los próximos días.
nudos y eslabones
-
Dado un diagrama planar para un nudo, ¿cuánto cuesta calcular: el polinomio de Alexander, el polinomio de Jones o el polinomio HOMFLYPT? ¿En qué medida se benefician de un ordenador cuántico?
-
Dado un diagrama planar para un nudo, ¿cuánto cuesta calcular una matriz de presentación para el módulo de Alexander? ¿Y las firmas de Tristram-Levine o Milnor?
-
¿Cuáles son los mejores tiempos de ejecución para el reconocimiento de nudos, como (cualquier versión modificada de) el algoritmo de Haken? El trabajo de Dynnikov sobre el reconocimiento de nudos también iría aquí.
-
¿Existen estimaciones de tiempo de ejecución sobre el tiempo que se tardaría en determinar si un nudo es una loncha o una cinta?
3manifolds
Todas estas preguntas asumen triangulaciones como entrada.
-
¿Cuánto cuesta el reconocimiento de 3 esferas? ¿La descomposición conecta-suma? (Jaco, Rubinstein, Burton, etc.)
-
¿Cuánto cuestan la descomposición compresión-cuerpo y la descomposición JSJ?
-
Qué tan costosa es la hiperbolización (para un 3manifold triangulado, hiperbolisable) es decir, el algoritmo cerrado+cusped Manning. (Manning, ?Tillman?, otros?)
-
¿Cuánto cuesta la geometrización? (?)
-
¿Es muy costoso calcular los ideales de Alexander de un 3manifold triangulado?
-
¿Cuánto cuesta producir una presentación quirúrgica de un 3manifold a partir de una triangulación? (El trabajo de D.Thurston y Costantino es el más relacionado con esto que conozco)
-
Dado un ordinal $n$ que representa el volumen de una hiperbólica $3$ -manifold de volumen finito, quiero saber el volumen real (como un número real). ¿Es difícil saberlo? ¿Qué tal reconstruir también el 3-manifold?
-
Dado un hiperbolisable cuspedo triangulado $3$ -¿existe un algoritmo eficiente para construir la descomposición de Epstein-Penner?
4-manifolds
-
Dada una 3-esfera de homología racional triangulada, ¿cuánto cuesta calcular el invariante de Rochlin generalizado? (o el invariante de Rochlin para una homología 3-esfera)
-
La misma pregunta, pero dada una presentación quirúrgica para la homología racional 3-esfera. En este caso existe el algoritmo de Kaplan.
-
¿Qué invariantes computables de los emparejamientos Farber-Levine existen, y cómo de difíciles son de calcular a partir de una presentación quirúrgica de una triangulación de un 4-manifold?
-
¿Es la Oszvath-Szabo ''d''-invariante de $spin^c$ ¿esferas homológicas racionales algorítmicamente computables ahora, dada una presentación quirúrgica? ¿Cómo son los tiempos de ejecución?
