Conventions: $\cong$ is homeomorphism of topological spaces and isomorphism of groups, $\equiv_G$ is the equality of two words over the generators of the group $G$. Simplicial complexes are finite.
Given two (abstract) simplicial complexes $K, L$, is it semidecidable whether their geometric realizations $|K|, |L|$ are homeomorphic, i.e. is there a computer program that, given $K, L$, eventually terminates if $|K| \cong |L|$, and never terminates if $|K| \not\cong |L|$?
If the problem is not semidecidable, then let me add an obvious continuation out of general interest. Fix a natural Gödel numbering $\mathrm{S} = f : \mathbb{N} \to \mbox{simplicial complexes}$. Let $p : \mathbb{N} \to \mathbb{N}^2$ be a natural bijection.
What is the position of the set $ E = \{ n \in \mathbb{N} \;|\; p(n) = (a,b), f(a) \cong f(b) \} $ in the lightface hierarchy of subsets of $\mathbb{N}$? Is this set in the arithmetical hierarchy?
My attempts below. I'm not an expert and these are based on a day or so of Googling, so I apologize for any misunderstandings.
It is a well-known result of Markov [Markov] that given two simplicial complexes, it is undecidable whether their geometric realizations are homeomorphic (and PL-homeomorphism is also undecidable [Poonen]).
According to Poonen [Poonen], here's an outline of the proof: There is an effective construction A that, from an f.p. group $G$ and a word $w$ over its generators, produces a simplicial complex $X_w$ such that if $w \equiv_G 1$ then $X_w \cong S^5$, while if $w \not\equiv_G 1$, then $X_w \not\cong S^5$.
This does not seem to help: Since the word problem of f.p. groups is semidecidable (uniformly in the description of the group and the word over generators), there is a uniform algorithm that, given any simplicial complex $C$ produced by construction A, solves its homeomorphism to $S^5$: enumerate all f.p. groups and words w over their generators, until you produce $C$, and semidecide $w \overset{?}{\equiv_G} 1$, which is correct assuming the previous construction A has the claimed property. (This algorithm is valid on all inputs, in the sense that it never mistakenly claims something is $S^5$ even if it is not produced by the algorithm of the previous paragraph.)
In [Lazarus] I find the following slightly different take: Given f.p. groups $G$, $H$ we produce combinatorial manifolds $X_G, X_H$ such that $X_G \cong X_H$ if and only if $G \cong H$.
This again does not seem to help: Isomorphism of f.p. groups is semidecidable, so again given two simplicial complexes produced by this method, simply enumerate pairs of f.p. groups, and once you find groups mapping to those complexes, semidecide their isomorphism.
Two simplicial complexes are called combinatorially equivalent if they have subdivisions that are isomorphic (bijection on vertices that induces a bijection on faces). This is semidecidable, just guess subdivisions and check isomorphism for each.
- This does not seem to help: A famous example of Milnor [Milnor] shows that there are examples of pairs of homeomorphic simplicial complexes which are not combinatorially equivalent.
If $f : |K| \to |L|$ is continuous, then there are subdivisions $K', L'$ of $K, L$ respectively, and a simplicial map $f' : K' \to L'$ such that $f'$ is homotopic to $f$ [Ranicki]. It follows that homotopy equivalence is semidecidable.
- This does not seem to help: there exist simplicial complexes which are homotopy equivalent but not homeomorphic, one example being $\{\{0\}\}$ and $\{\{0\}, \{1\}, \{0,1\}\}$.
It seems at least that $E$ is in $\Sigma^1_1$, i.e. lightface analytic. Just guess a rational approximation to a homeomorphism (and modulus of continuity?) I don't know much about levels this high, so my intuition may be off here. (In any case this is a bit too high, and seems to kind of defeat the point of combinatorial representations of topological spaces.)
About my application: I am dealing with a class of topological spaces that contains all finite simplicial complexes, so I can stop trying to semidecide their homeomorphism if the above problem is not semidecidable. I do not have a direct use for a semidecidability result, but by now I would be quite interested in this as well. Results that are intrinsically about PL-homeomorphism / simplicial homotopy&homology are not particularly useful to me because I don't know what the extension of those would be for my superclass, as it contains also e.g. Stone spaces so simplex embeddings are not very useful.
[Markov]: Markov, Andreï Andreyevich. "Insolubility of the problem of homeomorphy." In Dokl. Akad. Nauk SSSR, vol. 121, no. 195, p. 8. 1958.
[Poonen]: Poonen, Bjorn. "Undecidable problems: a sampler." Interpreting Gödel: Critical Essays (2014): 211-241.
[Lazarus]: Lazarus, Francis, and Arnaud de Mesmay. "Undecidability in Topology." (2017).
[Milnor]: Milnor, John. "Two complexes which are homeomorphic but combinatorially distinct." Annals of Mathematics (1961): 575-590.
[Ranicki]: Ranicki, A. A., A. Casson, D. Sullivan, M. Armstrong, C. Rourke, and G. Cooke. "The Hauptvermutung Book." Collection of papers by Casson, Sullivan, Armstrong, Cooke, Rourke and Ranicki, K-Monographs in Mathematics 1 (1996).
