Polynomial-time homology for simplicial Eilenberg-MacLane spaces (Q2441425): Difference between revisions

In an earlier paper [\textit{M. Čadek} et al., ``Computing all maps into a sphere'', Preprint, \url{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 \textit{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 \textit{S. Eilenberg} and \textit{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.