Abstract
A central problem of algebraic topology is to understand the homotopy groups πd(X)πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group π1(X)<math> <mrow><msub><mi>π</mi> <mn>1</mn></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X)<math> <mrow><msub><mi>π</mi> <mn>1</mn></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> trivial), compute the higher homotopy group πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> for any given d≥2<math><mrow><mi>d</mi> <mo>≥</mo> <mn>2</mn></mrow> </math> . However, these algorithms come with a caveat: They compute the isomorphism type of πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> , d≥2<math><mrow><mi>d</mi> <mo>≥</mo> <mn>2</mn></mrow> </math> as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere Sd<math><msup><mi>S</mi> <mi>d</mi></msup> </math> to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> and represents its elements as simplicial maps from a suitable triangulation of the d-sphere Sd<math><msup><mi>S</mi> <mi>d</mi></msup> </math> to X. For fixed d, the algorithm runs in time exponential in size(X)<math><mrow><mi>size</mi> <mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </math> , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d≥2<math><mrow><mi>d</mi> <mo>≥</mo> <mn>2</mn></mrow> </math> , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X)<math> <mrow><msub><mi>π</mi> <mi>d</mi></msub> <mrow><mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </mrow> </math> , the size of the triangulation of Sd<math><msup><mi>S</mi> <mi>d</mi></msup> </math> on which the map is defined, is exponential in size(X)<math><mrow><mi>size</mi> <mo>(</mo> <mi>X</mi> <mo>)</mo></mrow> </math> .