Algorithmically unsolvable problems in topology

Question

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.

Answer 1

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.

Answer 2

It seems pretty clear to me that if you fix $n$ and look at finite simply connected n-dimensional simplicial complexes then the (rational) homotopy equivalence problem is decidable. It's pretty clear that construction of (rational) Postnikov towers is algorithmic. Comparing two Postnikov towers is a sequence of obstruction problems, each decidable. And you don't need to compare full Postnikov towers, it's enough to compare up to height $n$ (the rest are determined automatically).

Answer 3

From "Hardness of embedding simplicial complexes in $\mathbb{R}^d$," by Matoušek, Tancer, Wagner, 2009 (PDF download link):

According to a celebrated result of Novikov ([VKF74]; also see, e.g., [Nab95] for an exposition), the following problem is algorithmically unsolvable: Given a $d$-dimensional simplicial complex, $d \ge 5$, decide whether it is homeomorphic to $\mathbb{S}^d$, the $d$-dimensional sphere.

• [VKF74] I.A. Volodin, V.E. Kuznetsov, and A.T. Fomenko. The problem of discriminating algorithmically the standard three-dimensional sphere. Usp. Mat. Nauk, 29(5):71–168, 1974. In Russian. English translation: Russ. Math. Surv. 29,5:71–172 (1974).
• [Nab95] A. Nabutovsky. Einstein structures: Existence versus uniqueness. Geom. Funct. Anal., 5(1):76–91, 1995.

In their paper, they prove that deciding whether or not a finite simplicial complex $K$ of dimension at most $k$, can be (piecewise linearly) embedded into $\mathbb{R}^d$, is NP-hard, for all $k, d$ with $d \ge 4$ and $d \ge k \ge (2d− 2)/3$.

Answer 4

I'm not sure whether these problems count as being topological: they're about topologically defined classes of groups:

Determining whether a presentation of a certain kind of knot groups in fact presents a more restrictive class of knots groups tends to be algorithmically unsolvable. I'm talking about the results in the paper Unsolvable problems about higher-dimensional knots and related groups by Francisco González Acuña, Cameron Gordon and Jonathan Simon:

Consider the classes of groups $\mathcal K_0 \subset \mathcal K_1 \subset \mathcal K_2 \subset \mathcal K_3 \subset \mathcal S \subset \mathcal M \subset \mathcal G$, where $\mathcal K_n$ is the class of fundamental groups of complements of $n$-spheres in $S^{n+2}$ (it is known that $\mathcal K_n = \mathcal K_3$ for $n\ge 3$); $\mathcal S$ (resp. $\mathcal M$, $\mathcal G$) is the class of fundamental groups of complements of orientable, closed surfaces in $S^4$ (resp. in a 1-connected 4-manifold, in a 4-manifold). (It is known that $\mathcal G$ is in fact the class of all finitely presented groups and that all the inclusions are strict.)

Their main theorem says that if $\mathcal B \subsetneq \mathcal A$ are two of the above classes of groups and $\mathcal K_3 \subseteq \mathcal A$, then there does not exist an algorithm that can decide, given a finite presentation of a group in $\mathcal A$ whether or not the group is in $\mathcal B$. And they conjecture this is true assuming only $\mathcal K_2 \subset \mathcal A$.