# Which properties of finite simplicial sets can be computed?

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.

• Are there any non-discrete finite Kan complexes? Apr 22, 2010 at 21:44
• This was stupid, there are no non-discrete finite Kan complexes. Thanks, Tilman. Apr 23, 2010 at 7:07
• So far sage seems to be able to compute with finite simplicial complexes and delta complexes . Some operations of spaces are implemented and CHomP can be used to compute their homology.  sagemath.org/doc/reference/homology.html Apr 23, 2010 at 7:11
• David Anick's paper "The computation of rational homotopy groups is #P-hard" discusses finite simply-connected CW complexes rather than simplicial sets; is that relevant? Apr 23, 2010 at 18:45
• Zisman deals with finite simplicial sets here: arxiv.org/abs/0909.2143 . Sep 30, 2010 at 8:50

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 , which is in Russian. That paper has an English review in the Journal of Symbolic Logic  that explicitly states the unsolvability of the homeomorphism and homotopy problems. For more modern work, see Nabutovsky and Weinberger . There is also a paper by Soare  that discusses some recursion-theoretic aspects of differential geometry and has a sketch of the proof that the homeomorphism problem is recursively unsolvable.

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

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

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

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

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.

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