Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I changed the ag tag to at (hopefully this was what was intended). –  Mark Grant Jun 2 '12 at 15:37
    
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. –  Mark Grant Jun 2 '12 at 17:17
    
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. –  Sergey Melikhov Jun 2 '12 at 18:20
    
Mark -- thanks, I did mean at, not ag. –  algori Jun 3 '12 at 16:50
add comment

4 Answers

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

share|improve this answer
    
Not only for rational spaces, in general Postnikov towers of simply connected finite CW-complexes are algorithmic. –  Fernando Muro Jun 2 '12 at 0:22
    
@Fernando Muro, yes, that's why I put rational in parentheses to include both cases. sorry of that was not clear. –  Vitali Kapovitch Jun 2 '12 at 1:34
    
Vitali -- I think you are right. Thanks. –  algori Jun 2 '12 at 4:22
4  
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. –  Tim Perutz Jun 2 '12 at 13:58
    
Tim -- thanks for the reference, that looks like what I was after. –  algori Jun 3 '12 at 16:49
add comment

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

share|improve this answer
    
Oh, I see now that this is mentioned by the OP. Consider this, then, merely adding detail. –  Joseph O'Rourke Jun 1 '12 at 23:53
    
@Joseph, note that Novikov's theorem does not assume simply connectednes and uses that fact very strongly. –  Vitali Kapovitch Jun 1 '12 at 23:55
    
@Vitali: I did not realize that aspect. Thank you for clarifying! –  Joseph O'Rourke Jun 1 '12 at 23:58
1  
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. –  Malte Jun 2 '12 at 22:32
add comment

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.

share|improve this answer
    
Thanks, Marek, this looks interesting. –  algori Feb 22 '13 at 13:53
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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