---
res:
bibo_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. @eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Martin
foaf_name: Čadek, Martin
foaf_surname: Čadek
- foaf_Person:
foaf_givenName: Marek
foaf_name: Krcál, Marek
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: Lukáš
foaf_name: Vokřínek, Lukáš
foaf_surname: Vokřínek
- foaf_Person:
foaf_givenName: Uli
foaf_name: Wagner, Uli
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
bibo_doi: 10.1145/2488608.2488683
dct_date: 2013^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: 'Extending continuous maps: Polynomiality and undecidability@'
...