Computing all maps into a sphere

article Computing all maps into a sphere published yes Martin Čadek author Marek Krcál author 33E21118-F248-11E8-B48F-1D18A9856A87 Jiří Matoušek author Francis Sergeraert author Lukáš Vokřínek author Uli Wagner author 36690CA2-F248-11E8-B48F-1D18A9856A870000-0002-1494-0568 UlWa department HeEd department Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X→ Y. We consider a computational version, where X,Y are given as finite simplicial complexes, and the goal is to compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected; in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or computing the Z2-index-everything in the stable range. Outside the stable range, the extension problem is undecidable. ACM2014 eng Journal of the ACM 1105.6257 00033720140000310.1145/2597629 613 M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” Journal of the ACM, vol. 61, no. 3. ACM, 2014. Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. Journal of the ACM. 2014;61(3). doi:<a href="https://doi.org/10.1145/2597629">10.1145/2597629</a> Čadek, Martin, et al. “Computing All Maps into a Sphere.” Journal of the ACM, vol. 61, no. 3, 17, ACM, 2014, doi:<a href="https://doi.org/10.1145/2597629">10.1145/2597629</a>. Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner, U. (2014). Computing all maps into a sphere. Journal of the ACM. ACM. <a href="https://doi.org/10.1145/2597629">https://doi.org/10.1145/2597629</a> Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing all maps into a sphere. Journal of the ACM. 61(3), 17. M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal of the ACM 61 (2014). Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere.” Journal of the ACM. ACM, 2014. <a href="https://doi.org/10.1145/2597629">https://doi.org/10.1145/2597629</a>. 21842018-12-11T11:56:12Z2025-09-29T11:34:15Z