Complejidad computacional del cálculo de grupos de homotopía de esferas

Question

En varias ocasiones he escuchado la afirmación de que computar la estructura del grupo de $\pi_k S^n$ es algoritmo . Pero nunca he encontrado una referencia que afirme esto.

¿Hay algún algoritmo preciso escrito en algún lugar de la literatura? ¿Hay alguno en la literatura, y si es así, cuáles son las estimaciones de tiempo de ejecución? Es de suponer que son bastante malas, ya que nadie parece mencionarlas.

¿Existen familias para las que haya mejores algoritmos, por ejemplo, para los grupos estables de homotopía de esferas? o $\pi_k S^2$ ?

edit: He hecho a Francis Sergeraert algunas preguntas relacionadas con su proyecto. Al parecer, todavía es una cuestión abierta en cuanto a si existe o no un algoritmo de tiempo de ejecución exponencial para calcular $\pi_k S^2$ .

Answer 1

Esto se aparta un poco de la cuestión que nos ocupa, pero creo que vale la pena hacer la observación. Consideremos la función de dos variables: $$ (X,n) \mapsto \pi_n X.$$ En función de $n$ la complejidad computacional se cree (para el general $X$ ) para crecer exponencialmente . Pero para los fijos $n$ como función de la conexión simple $X$ (medido en términos de, por ejemplo, número de símiles), el crecimiento de la complejidad computacional es polinomio .

(De hecho, supongo que incluso se puede especificar que el grado del polinomio sea algo así como $n/c$ donde $c$ es la conectividad del $X$ s. No sé si alguien ha hecho esa precisión).

Así que si quieres entrar en el juego de hacer algoritmos para calcular grupos de homotopía, no te molestes con esferas de alta dimensión: es una pérdida de esfuerzo. En su lugar, calcula grupos de homotopía de baja dimensión de espacios grandes. (Esto es básicamente lo que hace el "programa de homotopía efectiva" de Sergeraert, Rubio, Romero y otros).