25
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I changed the ag tag to at (hopefully this was what was intended). $\endgroup$
    – Mark Grant
    Jun 2, 2012 at 15:37
  • $\begingroup$ You might also be interested in "Complexity in rational homotopy" by Lechuga and Murillo. They show that various problems in rational homotopy are NP-hard. $\endgroup$
    – Mark Grant
    Jun 2, 2012 at 17:17
  • $\begingroup$ To anticipate Tim Perutz' more substantial comment below, the simply-connected homeomorphism problem for PL manifolds (and more) is done in the Nabutovsky-Weinberger paper arxiv.org/abs/math/9707232. $\endgroup$ Jun 2, 2012 at 18:20
  • $\begingroup$ Mark -- thanks, I did mean at, not ag. $\endgroup$
    – algori
    Jun 3, 2012 at 16:50

4 Answers 4

13
$\begingroup$

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.

$\endgroup$
0
6
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ Not only for rational spaces, in general Postnikov towers of simply connected finite CW-complexes are algorithmic. $\endgroup$ Jun 2, 2012 at 0:22
  • $\begingroup$ @Fernando Muro, yes, that's why I put rational in parentheses to include both cases. sorry of that was not clear. $\endgroup$ Jun 2, 2012 at 1:34
  • $\begingroup$ Vitali -- I think you are right. Thanks. $\endgroup$
    – algori
    Jun 2, 2012 at 4:22
  • 8
    $\begingroup$ This method is described by Nabutovsky and Weinberger in "Algorithmic aspects of homeomorphism problems", arxiv.org/abs/math/9707232. They point out a subtlety, though: one wants to compare the $(n+1)$st $k$-invariants, not on the nose, but up to the action of the homotopy self-equivalences of the $n$th stage. That involves deciding whether two vectors in some tensor representation of an arithmetic group lie in the same orbit. This is algorithmically decidable, but not obviously so. $\endgroup$
    – Tim Perutz
    Jun 2, 2012 at 13:58
  • $\begingroup$ Tim -- thanks for the reference, that looks like what I was after. $\endgroup$
    – algori
    Jun 3, 2012 at 16:49
5
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Oh, I see now that this is mentioned by the OP. Consider this, then, merely adding detail. $\endgroup$ Jun 1, 2012 at 23:53
  • $\begingroup$ @Joseph, note that Novikov's theorem does not assume simply connectednes and uses that fact very strongly. $\endgroup$ Jun 1, 2012 at 23:55
  • $\begingroup$ @Vitali: I did not realize that aspect. Thank you for clarifying! $\endgroup$ Jun 1, 2012 at 23:58
  • 2
    $\begingroup$ The theorem of S.P. Novikov actually asserts that one cannot distinguish homology spheres from the standard sphere if $n\geq 5$. There is a generalization to this due to Nabutovsky--Weinberger asserting that S.P. Novikov's theorem remains valid in the presence of a lower bound on simplicial volume. $\endgroup$
    – Malte
    Jun 2, 2012 at 22:32
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.