[Math] Which properties of finite simplicial sets can be computed

at.algebraic-topologycomputability-theorygn.general-topologyhomotopy-theorysimplicial-stuff

A simplicial set $X$ is a a combinatorial model for a topological space $|X|$, its realization, and conversely every topological space is weakly equivalent to such a realization of a simplicial set. I am wondering, which properties of finite simplicial sets can be effectively (or even theoretically) computed using a computer program. Maybe there are some implementations and I am not aware of their existence, so I would be very pleased about any information.

The first problem is how to input the simplicial set (maybe that's not really a problem).

Does one know terminating algorithms for the following problems then? Are there other problems for which anything is known in this direction?

  1. Is a given finite simplicial set a Kan complex?
  2. Given two finite simplicial sets $X$ and $Y$, are $|X|$ and $|Y|$ homeomorphic?
  3. Given two finite simplicial sets $X$ and $Y$, are $|X|$ and $|Y|$ homotopy equivalent?
  4. What are the homotopy/homology groups of a given Kan complex?
  5. Given a finite simplicial set $X$, what are the homotopy/homology groups of $|X|$?

etc.

Best Answer

For homeomorphism equivalence and homotopy equivalence, the associated problems are recursively unsolvable. This fact dates back to Markov in the 1950s, and relies on the unsolvability of the word problem for finitely presented groups. Apparently it was proved in Markov [1], which is in Russian. That paper has an English review in the Journal of Symbolic Logic [2] that explicitly states the unsolvability of the homeomorphism and homotopy problems. For more modern work, see Nabutovsky and Weinberger [3]. There is also a paper by Soare [4] that discusses some recursion-theoretic aspects of differential geometry and has a sketch of the proof that the homeomorphism problem is recursively unsolvable.

[1] MARKOV, AA: 'On the unsolvability of certain problems in topology', Dokl. Akad Nauk SSSR 123, no. 6 (1958), 978-980

[2] The Journal of Symbolic Logic, Vol. 37, No. 1 (Mar., 1972), p. 197

[3] Alexander Nabutovsky and Shmuel Weinberger, "Algorithmic aspects of homeomorphism problems", http://arxiv.org/abs/math/9707232

[4] Robert I. Soare, "Computability theory and differential geometry", http://people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Related Question