Extending continuous maps: Polynomiality and undecidability

Čadek, Martin and Krčál, Marek and Matoušek, Jiří and Vokřínek, Lukáš and Wagner, Uli (2013) Extending continuous maps: Polynomiality and undecidability. In: STOC: Symposium on Theory of Computing, June 1-4, 2013, Palo Alto, CA, USA.

[img] Text
Extending_continuous_maps_polynomiality_and_undecidability.pdf - Accepted Version
Available under License All rights reserved.
Download (437Kb)
Official URL: http://dx.doi.org/10.1145/2488608.2488683


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.

Item Type: Conference or Workshop Item (Paper)
Additional Information: © Wagner | ACM 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in STOC: Theory of Computing, http://dx.doi.org/10.1145/2488608.2488683/10.1145.
Uncontrolled Keywords: Algebraic topology, Extendability, Homotopy groups, Homotopy theory
Subjects: 500 Science > 510 Mathematics
Research Group: Wagner Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 04 May 2016 09:50
Last Modified: 05 Sep 2017 14:42
URI: https://repository.ist.ac.at/id/eprint/533

Actions (login required)

View Item View Item