In an earlier paper [M. Čadek et al., “Computing all maps into a sphere”, Preprint, arXiv:1105.6257], the authors and their coauthors have developed an algorithm for a problem in computational algebraic topology to compute the set (or group) \([X,Y]\) of all homotopy classes of continuous maps from \(X\) to \(Y\).
A simplicial set \(X\) parameterized by a set \(\mathcal I\) is equipped with polynomial-time homology if (1) \(X\) is locally polynomial-time; (2) there is a locally polynomial-time chain complex \(EC_*\) such that, for each fixed \(k\), the distinguished basis \(B(I)_k\) of \(EC(I)_k\) can be computed in time polynomial in \(\mathrm{size}(I)\), the number of bits in the encoding, and the rank \(r(I)_k\) is bounded by such a polynomial; and (3) for every \(I \in \mathcal I\), there is a reduction (a contraction in the sense of S. Eilenberg and S. MacLane [Ann. Math. (2) 58, 55–106 (1953; Zbl 0050.39304)]) \(\rho_I = (f_I, g_I, h_I)\) from \(C_*(X(I))\) to \(EC(I)_*\), where the maps \((f_I)k, (g_I)_k\) and \((h_I)_k\) of \(\rho_I\) are all computable in time bounded by a polynomial in \(\mathrm{size}(I)\) plus the size of the input \(k\)-chain.
In the present paper, the authors construct a suitable discrete vector field, in the sense of Forman’s discrete Morse theory, on the Eilenberg-MacLane space \(K(\mathbb{Z},1)\), which is homotopy equivalent to the unit circle \(S^1\). The construction here is purely combinatorial. The authors show that the Eilenberg-MacLane space \(K(\mathbb{Z},1)\), represented as a simplicial group, can be equipped with polynomial-time homology. They prove that if the dimensions of a locally polynomial-time simplicial set \(X\) are bounded by a constant, then \(X\) can be turned into a simplicial set with polynomial-time homology. The paper is well written and organized.