# Extending continuous maps: Polynomiality and undecidability

Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of computing. STOC: Symposium on the Theory of Computing, 595–604.

Download

IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf
447.94 KB
[Submitted Version]

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Department

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.

Publishing Year

Date Published

2013-06-01

Proceedings Title

45th Annual ACM Symposium on theory of computing

Page

595 - 604

Conference

STOC: Symposium on the Theory of Computing

Conference Location

Palo Alto, CA, United States

Conference Date

2013-06-01 – 2013-06-04

IST-REx-ID

### Cite this

Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps: Polynomiality and undecidability. In:

*45th Annual ACM Symposium on Theory of Computing*. ACM; 2013:595-604. doi:10.1145/2488608.2488683Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., & Wagner, U. (2013). Extending continuous maps: Polynomiality and undecidability. In

*45th Annual ACM Symposium on theory of computing*(pp. 595–604). Palo Alto, CA, United States: ACM. https://doi.org/10.1145/2488608.2488683Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. “Extending Continuous Maps: Polynomiality and Undecidability.” In

*45th Annual ACM Symposium on Theory of Computing*, 595–604. ACM, 2013. https://doi.org/10.1145/2488608.2488683.M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous maps: Polynomiality and undecidability,” in

*45th Annual ACM Symposium on theory of computing*, Palo Alto, CA, United States, 2013, pp. 595–604.Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.”

*45th Annual ACM Symposium on Theory of Computing*, ACM, 2013, pp. 595–604, doi:10.1145/2488608.2488683.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

Access Level

Open Access

Date Uploaded

2018-12-12

MD5 Checksum

06c2ce5c1135fbc1f71ca15eeb242dcf