# zbMATH — the first resource for mathematics

Extendability of continuous maps is undecidable. (English) Zbl 1358.68297
Summary: 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\subseteq X$$, and a (continuous) map $$f:A\rightarrow Y$$, decide whether $$f$$ can be extended to a continuous map $$\bar{f}: X\to Y$$. 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\geq 2$$, the extension problem is algorithmically solvable if the dimension of $$X$$ is at most $$2k - 1$$, and even in polynomial time when $$k$$ is fixed.
Here we show that the condition $$\dim X\leq 2k-1$$ cannot be relaxed: for $$\dim X=2k$$, 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 D. J. Anick [Lect. Notes Pure Appl. Math. 114, 1–56 (1989; Zbl 0691.55009)], says that the computation of $$\pi _{k }(Y)$$ of a 1-connected simplicial complex $$Y$$ is #P-hard when $$k$$ is considered as a part of the input.

##### MSC:
 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 03D35 Undecidability and degrees of sets of sentences 55Q52 Homotopy groups of special spaces 55U10 Simplicial sets and complexes in algebraic topology 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity
Full Text: