Filakovský Marek, Franek Peter, Wagner Uli, Zhechev Stephan
IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria.
J Appl Comput Topol. 2018;2(3):177-231. doi: 10.1007/s41468-018-0021-5. Epub 2018 Sep 25.
A central problem of algebraic topology is to understand the of a topological space . For the computational version of the problem, it is well known that there is no algorithm to decide whether the of a given finite simplicial complex is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex that is (i.e., with trivial), compute the higher homotopy group for any given . However, these algorithms come with a caveat: They compute the isomorphism type of , as an finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of . Converting elements of this abstract group into explicit geometric maps from the -dimensional sphere to has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space , computes and represents its elements as simplicial maps from a suitable triangulation of the -sphere to . For fixed , the algorithm runs in time exponential in , the number of simplices of . Moreover, we prove that this is optimal: For every fixed , we construct a family of simply connected spaces such that for any simplicial map representing a generator of , the size of the triangulation of on which the map is defined, is exponential in .
代数拓扑学的一个核心问题是理解拓扑空间的 。对于该问题的计算版本，众所周知，不存在一种算法来判定给定有限单纯复形的 是否平凡。另一方面，有几种算法，给定一个有限单纯复形 （即 平凡），能计算出任意给定 时的高阶同伦群 。然而，这些算法有一个警告：它们计算 的同构类型， 作为一个由生成元和关系给出的有限生成阿贝尔群，但它们处理 元素的表示非常隐式。将这个抽象群的元素转化为从 维球面 到 的显式几何映射，一直是计算同伦理论新兴领域的主要未解决问题之一。在这里，我们给出一种算法，给定一个单连通空间 ，计算 并将其元素表示为从 的合适三角剖分到 的单纯映射。对于固定的 ，该算法的运行时间是 的指数函数， 是 的单纯形数量。此外，我们证明这是最优的：对于每个固定的 ，我们构造一族单连通空间 ，使得对于任何表示 生成元的单纯映射，该映射所定义的 的三角剖分的大小是 的指数函数。
