--- res: bibo_abstract: - We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d - 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere S d), and dim X ≤ 2d - 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ 2-index, which is a quantity playing a prominent role in Borsuk-Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝ d also amounts to a ℤ 2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Martin foaf_name: Čadek, Martin foaf_surname: Čadek - foaf_Person: foaf_givenName: Marek foaf_name: Marek Krcál foaf_surname: Krcál foaf_workInfoHomepage: http://www.librecat.org/personId=33E21118-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: Jiří foaf_name: Matoušek, Jiří foaf_surname: Matoušek - foaf_Person: foaf_givenName: Francis foaf_name: Sergeraert, Francis foaf_surname: Sergeraert - foaf_Person: foaf_givenName: Lukáš foaf_name: Vokřínek, Lukáš foaf_surname: Vokřínek - foaf_Person: foaf_givenName: Uli foaf_name: Uli Wagner foaf_surname: Wagner foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-1494-0568 dct_date: 2012^xs_gYear dct_publisher: SIAM@ dct_title: Computing all maps into a sphere@ ...