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