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

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.

share|improve this question
    
Why is this community wiki? –  François G. Dorais Apr 22 '10 at 18:33
1  
Are there any non-discrete finite Kan complexes? –  Tilman Apr 22 '10 at 21:44
    
This was stupid, there are no non-discrete finite Kan complexes. Thanks, Tilman. –  user4676 Apr 23 '10 at 7:07
    
So far sage seems to be able to compute with finite simplicial complexes and delta complexes [1]. Some operations of spaces are implemented and CHomP can be used to compute their homology. [1] sagemath.org/doc/reference/homology.html –  user2146 Apr 23 '10 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? –  John Palmieri Apr 23 '10 at 18:45

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.