Extending continuous maps: Polynomiality and undecidability Conference Paper

Author(s): Čadek, Martin; Krčál, Marek; Matoušek, Jiří; Vokřínek, Lukáš; Wagner, Uli
Title: Extending continuous maps: Polynomiality and undecidability
Affiliation IST Austria
Abstract: We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex.
Keywords: Algebraic topology; Extendability; Homotopy groups; Homotopy theory
Conference Title: STOC: Symposium on the Theory of Computing
Conference Dates: June 1-4, 2013
Conference Location: Palo Alto, CA, USA
ISBN: 978-145033536-2
Publisher: ACM  
Location: New York, NY, USA
Date Published: 2013-06-01
Start Page: 595
End Page: 604
DOI: 10.1145/2488608.2488683
Notes: We would like to thank Francis Sergeraert for many useful discussions and extensive advice; although he chose not to be listed as a co-author of this survey,his contribution is significant, notspeaking of his leading role in the development of effective homology, which constitutes the foundation of our algorithmic methods. We also thank Marek Filakovsk ́y for useful discussions, and J. Maurice Rojas for kind replies to our questions concerning variants of Hilbert’s tenth problem.
Open access: yes (repository)
IST Austria Authors
  1. Uli Wagner
    46 Wagner
  2. Marek Krčál
    10 Krčál
Related IST Austria Work