Extendability of Continuous Maps Is Undecidable

• Published in: Discrete & computational geometry 2014, Vol.51 (1), p.24-66
• Main Authors: Čadek, Martin, Krčál, Marek, Matoušek, Jiří, Vokřínek, Lukáš, Wagner, Uli
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Applied mathematics; Combinatorics; Computation; Computational Mathematics and Numerical Analysis; Geometry; Mathematical analysis; Mathematics; Mathematics and Statistics; Polynomials; Texts; Topology
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-013-9551-8

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups , from the point of view of computability and computational complexity. The extension problem is the following: Given topological spaces X and Y , a subspace A ⊆ X , and a (continuous) map f : A → Y , decide whether f can be extended to a continuous map . All spaces are given as finite simplicial complexes, and the map f is simplicial. Recent positive algorithmic results, proved in a series of companion papers, show that for ( k −1)-connected Y , k ≥2, the extension problem is algorithmically solvable if the dimension of X is at most 2 k −1, and even in polynomial time when k is fixed. Here we show that the condition cannot be relaxed: for , the extension problem with ( k −1)-connected Y becomes undecidable. Moreover, either the target space Y or the pair ( X , A ) can be fixed in such a way that the problem remains undecidable. Our second result, a strengthening of a result of Anick, says that the computation of π k ( Y ) of a 1-connected simplicial complex Y is #P-hard when k is considered as a part of the input.