000203937 001__ 203937
000203937 005__ 20181203023715.0
000203937 0247_ $$2doi$$a10.1137/120899029
000203937 022__ $$a0097-5397 000203937 02470$$2ISI$$a000344753500009 000203937 037__$$aARTICLE
000203937 245__ $$aPolynomial-Time Computation Of Homotopy Groups And Postnikov Systems In Fixed Dimension 000203937 269__$$a2014
000203937 260__ $$bSiam Publications$$c2014$$aPhiladelphia 000203937 300__$$a53
000203937 336__ $$aJournal Articles 000203937 520__$$aFor 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.
000203937 6531_ $$aalgebraic topology 000203937 6531_$$ahomotopy theory
000203937 6531_ $$ahomotopy groups 000203937 6531_$$aPostnikov systems
000203937 6531_ $$acomputational complexity 000203937 700__$$uMasaryk Univ, Dept Math & Stat, CS-61137 Brno, Czech Republic$$aCadek, Martin 000203937 700__$$uCharles Univ Prague, Dept Appl Math, CR-11800 Prague 1, Czech Republic$$aKrcal, Marek 000203937 700__$$uETH, Dept Comp Sci, CH-8092 Zurich, Switzerland$$aMatousek, Jiri 000203937 700__$$uMasaryk Univ, Dept Math & Stat, CS-61137 Brno, Czech Republic$$aVokrinek, Lukas 000203937 700__$$aWagner, Uli
000203937 773__ $$j43$$tSiam Journal On Computing$$k5$$q1728-1780
000203937 909C0 $$0252438$$pMATHGEOM$$xU10159 000203937 909CO$$particle$$ooai:infoscience.tind.io:203937 000203937 937__$$aEPFL-ARTICLE-203937
000203937 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL 000203937 980__$$aARTICLE