Abstract We present an algorithm that, given finite diagrams of simplicial sets X, A, Y, i.e., functors $${\mathcal {I}}^\textrm{op}\rightarrow {\textsf {s}} {\textsf {Set}}$$ I op → s Set , such that (X, A) is a cellular pair, $$\dim X\le 2\cdot {\text {conn}}Y$$ dim X ≤ 2 · conn Y , $${\text {conn}}Y\ge 1$$ conn Y ≥ 1 , computes the set $$[X,Y]^A$$ [ X , Y ] A of homotopy classes of maps of diagrams $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given $$f:A\rightarrow Y$$ f : A → Y . For fixed $$n=\dim X$$ n = dim X , the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf’s theorem, we deduce an algorithm that, given finite simplicial sets X, A, Y with an action of a finite group G, computes the set $$[X,Y]^A_G$$ [ X , Y ] G A of homotopy classes of equivariant maps $$\ell :X\rightarrow Y$$ ℓ : X → Y extending a given equivariant map $$f:A\rightarrow Y$$ f : A → Y under the stability assumption $$\dim X^H\le 2\cdot {\text {conn}}Y^H$$ dim X H ≤ 2 · conn Y H and $${\text {conn}}Y^H\ge 1$$ conn Y H ≥ 1 , for all subgroups $$H\le G$$ H ≤ G . Again, for fixed $$n=\dim X$$ n = dim X , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a k-dimensional simplicial complex K, is there a map $$K\rightarrow {\mathbb {R}}^d$$ K → R d without r-tuple intersection points? In the metastable range of dimensions, $$rd\ge (r+1) k+3$$ r d ≥ ( r + 1 ) k + 3 , the problem is shown algorithmically decidable in polynomial ti

Given topological spaces X , Y , a fundamental problem of algebraic topology is understanding the structure of all continuous maps X → Y . We consider a computational version, where X , Y are given as finite simplicial complexes, and the goal is to compute [ X , Y ], that is, all homotopy classes of such maps. We solve this problem in the stable range , where for some d ≥ 2, we have dim X ≤ 2 d −2 and Y is ( d -1)- connected ; in particular, Y can be the d -dimensional sphere S d . The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [ X , Y ] is known to be uncomputable for general X , Y , since for X = S 1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y . In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem , where we are given a subspace A ⊂ X and a map A → Y and ask whether it extends to a map X → Y , or computing the ℤ 2 - index —everything in the stable range. Outside the stable range, the extension problem is undecidable.

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed $k\ge 2$, there is a polynomial-time algorithm that, for a $1$-connected topological space $X$ given as a finite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the $k$th homotopy group $\pi_k(X)$, as well as the first $k$ stages of a Postnikov system of $X$. Combined with results of an earlier paper, this yields a polynomial-time computation of $[X,Y]$, i.e., all homotopy classes of continuous mappings $X\to Y$, under the assumption that $Y$ is $(k-1)$-connected and $\dim X\le 2k-2$. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes $X$, $Y$, where $Y$ is $(k-1)$-connected and $\dim X\le 2k-1$, plus a subspace $A\subseteq X$ and a (simplicial) map $f:A\to Y$, and the question is the extendability of $f$ to all of $X$. The algorithms are based on the notion of a simplicial set with polynomial-time homology, which is an enhancement of the notion of a simplicial set with effective homology developed earlier by Sergeraert and his coworkers. Our polynomial-time algorithms are obtained by showing that simplicial sets with polynomial-time homology are closed under various operations, most notably Cartesian products, twisted Cartesian products, and classifying space. One of the key components is also polynomial-time homology for the Eilenberg--MacLane space $K(\mathbb{Z},1)$, provided in another recent paper by Krčál, Matoušek, and Sergeraert. (A corrected file is attached.)

We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity.

We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d − 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere Sd), and dim X ≤ 2d − 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ2-index, which is a quantity playing a prominent role in Borsuk–Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝd also amounts to a ℤ2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.