This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various areas of mathematics.
The topology part however contains only two such problems: the homeomorphism problem for 4-manifolds, which was shown to be undecidalbe by Markov in 1958, and the problem of recognizing $S^n,n\geq 5$ up to homeomorphism. The indecidability in both cases basically boils down to the undecidability of the group isomorphism problem.
Note that both the above problems become decidable if one restricts one's attention to simply-connected PL-manifolds. This follows in the first case from the fact that simply-connected PL 4-manifolds are determined up to homeomorphism by the integral cohomology and in the second case from the generalized Poincare conjecture.
This makes one wonder what happens if one imposes some natural topological restrictions like simple connectedness. So I would like to ask if the following problems are decidable for simply-connected finite simplicial complexes, maybe under some further restrictions (e.g. for those those simplicial complexes that are homeomorphic to smooth or PL-manifolds):
-
the homeomorphism problem
-
the homotopy equivalence problem
-
the rational (or mod a prime $p$) homotopy equivalence problem
Personally, I do not hold out much hope that any of these turns out to be algorithmically decidable. For instance, the rational homotopy type of a space $X$ can be seen as an infinite collection of maps $H^{\otimes n}\to H$ of degrees $2-n$ (where $H=H^*(X,\mathbb{Q})$) subject to some condition, up to an equivalence relation, and it looks plausible that all the components in this collection matter. However, it is not completely clear to me how to prove this.
Best Answer
Yesterday we submitted on http://arxiv.org/abs/1302.2370 a paper "Extendability of continuous maps is undecidable" claiming that the following problem is undecidable: Given simplicial complexes $X$ and $Y$ and a simplicial map $f:A\to Y$ from a subcomplex $A$ of $X$, decide whether there is a continuous extension $|X|\to |Y|$ of $|f|$. Substantial features:
the undecidability is show by a reduction from the Hilbert's 10th problem, that is, solvability of Diophantine polynomial equation
the undecidability holds even if we require the considered spaces to be $k$-connected for arbitrary $k\ge 1$
Notably, once the dimension of $X$ is less than $2k$ where $k$ is the connectivity of $Y$ (stable range), the problem becomes solvable (in polynomial time when $k$ is fixed), see http://arxiv.org/abs/1211.3093.