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]
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]
References
- ^ Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72, Springer, p. 247, ISBN 9780387979700.
- ^ Poonen, Bjorn (2014-10-25). "Undecidable problems: a sampler". arXiv:1204.0299 [math].
- ^ "A. Markov, "The insolubility of the problem of homeomorphy", Dokl. Akad. Nauk SSSR, 121:2 (1958), 218–220". www.mathnet.ru. Retrieved 2022-11-27.