التفاصيل البيبلوغرافية
| العنوان: |
POLYNOMIAL-TIME COMPUTATION OF HOMOTOPY GROUPS AND POSTNIKOV SYSTEMS IN FIXED DIMENSION. |
| المؤلفون: |
ČADEK, MARTIN1 cadek@math.muni.cz, KRČAL, MAREK2 krcal@kam.mff.cuni.cz, MATOUŠEK, JIŘÍ3 matousek@kam.mff.cuni.cz, VOKŘÍNEK, LUKÁŠ4, WAGNER, ULI4 uli.wagner@gmail.com |
| المصدر: |
SIAM Journal on Computing. 2014, Vol. 43 Issue 5, p1728-1780. 53p. |
| مصطلحات موضوعية: |
*COMPUTER algorithms, ALGEBRAIC topology, HOMOTOPY theory, POLYNOMIAL time algorithms, COMPUTATIONAL complexity |
| مستخلص: |
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 π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 dimX ≤ 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 dimX ≤ 2k-1, plus a subspace A ⊆ 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(ℤ, 1), provided in another recent paper by Krčál, Matoušek, and Sergeraert. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
