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

0479819 - ÚI 2018 US eng J - Článek v odborném periodiku
Čadek, M. - Krčál, Marek - Matoušek, J. - Vokřínek, L. - Wagner, U.
Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension.
Siam Journal on Computing. Roč. 43, č. 5 (2014), s. 1728-1780. ISSN 0097-5397. E-ISSN 1095-7111
Klíčová slova: algebraic-topology * computability * maps * algebraic topology * homotopy theory * homotopy groups * Postnikov systems * computational complexity
Impakt faktor: 0.741, rok: 2014

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k >= 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 kth 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> Y, under the assumption that Y is (k 1)-connected and dim X <= 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 <= 2k 1, plus a subspace A subset of X and a (simplicial) map f : A> 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(Z, 1), provided in another recent paper by Krcal, Matousek, and Sergeraert.
Trvalý link: http://hdl.handle.net/11104/0275746