Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension

• Published in: SIAM journal on computing 2014-01, Vol.43 (5), p.1728-1780
• Main Authors: Čadek, Martin, Krčál, Marek, Matoušek, Jiří, Vokřínek, Lukáš, Wagner, Uli
• Format: Article
• Language: English
• Subjects: Algorithms; Cartesian; Classification; Computation; Homology; Mathematical analysis; Polynomials; Running
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/120899029

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 theextension 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 asimplicial 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 Krcal, Matousek, and Sergeraert.