Simplicial complex recognition problem
The simplicial complex recognition problem is a computational problem in algebraic topology. Given a simplicial complex, the problem is to decide whether it is homeomorphic to another fixed simplicial complex. The problem is undecidable for complexes of dimension 5 or more.[1][2](pp9–11)
Background
An abstract simplicial complex (ASC) is family of sets that is closed under taking subsets (the subset of a set in the family is also a set in the family). Every abstract simplicial complex has a unique geometric realization in a Euclidean space as a geometric simplicial complex (GSC), where each set with k elements in the ASC is mapped to a (k-1)-dimensional simplex in the GSC. Thus, an ASC provides a finite representation of a geometric object. Given an ASC, one can ask several questions regarding the topology of the GSC it represents.
Homeomorphism problem
The homeomorphism problem is: given two finite simplicial complexes representing smooth manifolds, decide if they are homeomorphic.
- If the complexes are of dimension at most 3, then the problem is decidable. This follows from the proof of the geometrization conjecture.
- For every d ≥ 4, the homeomorphism problem for d-dimensional simplicial complexes is undecidable.[3]
The same is true if "homeomorphic" is replaced with "piecewise-linear homeomorphic".
Recognition problem
The recognition problem is a sub-problem of the homeomorphism problem, in which one simplicial complex is given as a fixed parameter. Given another simplicial complex as an input, the problem is to decide whether it is homeomorphic to the given fixed complex.
- The recognition problem is decidable for the 3-dimensional sphere [math]\displaystyle{ S^3 }[/math].[4] That is, there is an algorithm that can decide whether any given simplicial complex is homeomorphic to the boundary of a 4-dimensional ball.
- The recognition problem is undecidable for the d-dimensional sphere [math]\displaystyle{ S^d }[/math] for any d ≥ 5. The proof is by reduction from the word problem for groups. From this, it can be proved that the recognition problem is undecidable for any fixed compact d-dimensional manifold with d ≥ 5.
- As of 2014, it is open whether the recognition problem is decidable for the 4-dimensional sphere [math]\displaystyle{ S^4 }[/math].[2](pp11)
Manifold problem
The manifold problem is: given a finite simplicial complex, is it homeomorphic to a manifold? The problem is undecidable; the proof is by reduction from the word problem for groups.[2](pp11)
References
- ↑ Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, 72, Springer, p. 247, ISBN 9780387979700, https://books.google.com/books?id=265lbM42REMC&pg=PA247.
- ↑ 2.0 2.1 2.2 Poonen, Bjorn (2014-10-25). "Undecidable problems: a sampler". arXiv:1204.0299 [math.LO].
- ↑ "A. Markov, "The insolubility of the problem of homeomorphy", Dokl. Akad. Nauk SSSR, 121:2 (1958), 218–220". https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=23250&option_lang=eng.
- ↑ Matveev, Sergei (2003), Matveev, Sergei, ed., "Algorithmic Recognition of S3" (in en), Algorithmic Topology and Classification of 3-Manifolds, Algorithms and Computation in Mathematics (Berlin, Heidelberg: Springer) 9: pp. 193–214, doi:10.1007/978-3-662-05102-3_5, ISBN 978-3-662-05102-3, https://doi.org/10.1007/978-3-662-05102-3_5, retrieved 2022-11-27
 |  |
