Access Restriction

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

   Open content in new tab
Source: ACM Digital Library