Extendability of Continuous Maps Is Undecidable

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 $\bar{f}\colon 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≥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 $\mathop{\mathrm{dim}}\nolimits X\leq 2k-1$ cannot be relaxed: for $\mathop{\mathrm{dim}}\nolimits 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 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.