### Computing All Maps into a SphereComputing All Maps into a Sphere

Access Restriction
Subscribed

 Author Čadek, Martin ♦ Krčál, Marek ♦ Matouek, Ji ♦ Sergeraert, Francis ♦ Voknek, Luk ♦ Wagner, Uli Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational topology ♦ Homotopy groups ♦ Postnikov systems Abstract Given topological spaces $\textit{X},\textit{Y},$ a fundamental problem of algebraic topology is understanding the structure of all continuous maps $\textit{X}$ → $\textit{Y}.$ We consider a computational version, where $\textit{X},\textit{Y}$ are given as finite simplicial complexes, and the goal is to compute $[\textit{X},\textit{Y}],$ that is, all homotopy classes of such maps. We solve this problem in the stable range, where for some $\textit{d}$ ≥ 2, we have dim $\textit{X}$ ≤ $2\textit{d}™2$ and $\textit{Y}$ is $(\textit{d}-1)-\textit{connected};$ in particular, $\textit{Y}$ can be the $\textit{d}-dimensional$ sphere $S^{d}.$ 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, $[\textit{X},\textit{Y}]$ is known to be uncomputable for general $\textit{X},\textit{Y},$ since for $X=S^{1}$ it includes a well known undecidable problem: testing triviality of the fundamental group of $\textit{Y}.$ In follow-up papers, the algorithm is shown to run in polynomial time for $\textit{d}$ fixed, and extended to other problems, such as the extension problem, where we are given a subspace $\textit{A}$ ⊂ $\textit{X}$ and a map $\textit{A}$ → $\textit{Y}$ and ask whether it extends to a map $\textit{X}$ → $\textit{Y},$ or computing the $ℤ_{2}-index—everything$ in the stable range. Outside the stable range, the extension problem is undecidable. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-06-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 3 Page Count 44 Starting Page 1 Ending Page 44

#### Open content in new tab

Source: ACM Digital Library