Which properties of finite simplicial sets can be computed?

Question

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.

Answer 1

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

Answer 2

Francis Sergeraert seems to have done a lot of work on these types of questions. In particular he has written a Lisp program, Kenzo, to work with simplicial sets. The program looks very interesting but as of yet I haven't spent much time with it. So I can't say firsthand what it's good at.

Answer 3

In the simply connected case, essentially everything is in principle computable, by some very early work of E.H. Brown:

\bib{MR0083733}{article}{
   author={Brown, Edgar H., Jr.},
   title={Finite computability of Postnikov complexes},
   journal={Ann. of Math. (2)},
   volume={65},
   date={1957},
   pages={1--20},
   issn={0003-486X},
   review={\MR{0083733 (18,753a)}},
}

In particular, if $X$ and $Y$ are finite simplicial complexes then $[\Sigma^n X,\Sigma^n Y]$ is computable for $n\geq 2$, and for large $n$ this gives the group of stable homotopy classes of maps. However, I do not think that there are practical algorithms for many such questions, although I am not up to date on this. Probably the simplest case that I do not know is as follows: is there a practical algorithm to compute the complex $K$-theory $K^0(X)$ for a finite simplicial complex $X$?