View source for Simplicial complex recognition problem

{{Short description|Computational problem in algebraic topology}}
The '''simplicial complex recognition problem''' is a [[Computational problem|computational problem]] in [[Algebraic topology|algebraic topology]]. Given a [[Simplicial complex|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.<ref>{{citation |last=Stillwell |first=John |title=Classical Topology and Combinatorial Group Theory |url=https://books.google.com/books?id=265lbM42REMC&pg=PA247 |volume=72 |page=247 |year=1993 |series=Graduate Texts in Mathematics |publisher=Springer |isbn=9780387979700 |authorlink=John Stillwell}}.</ref><ref name=":0">{{cite arXiv |last=Poonen |first=Bjorn |date=2014-10-25 |title=Undecidable problems: a sampler |class=math.LO |eprint=1204.0299 }}</ref>{{Rp|pages=9–11}}

== Background ==
An [[Abstract simplicial complex|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 [[Homeomorphism (graph theory)|homeomorphic]].

* If the complexes are of dimension at most 3, then the problem is decidable. This follows from the proof of the [[Geometrization conjecture|geometrization conjecture]].
* For every d ≥ 4, the homeomorphism problem for ''d''-dimensional simplicial complexes is undecidable.<ref>{{Cite web |title=A. Markov, "The insolubility of the problem of homeomorphy", Dokl. Akad. Nauk SSSR, 121:2 (1958), 218–220 |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=23250&option_lang=eng |access-date=2022-11-27 |website=www.mathnet.ru}}</ref>
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>S^3</math>.<ref>{{Citation |last=Matveev |first=Sergei |title=Algorithmic Recognition of S3 |date=2003 |url=https://doi.org/10.1007/978-3-662-05102-3_5 |work=Algorithmic Topology and Classification of 3-Manifolds |series=Algorithms and Computation in Mathematics |volume=9 |pages=193–214 |editor-last=Matveev |editor-first=Sergei |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-662-05102-3_5 |isbn=978-3-662-05102-3 |access-date=2022-11-27}}</ref> 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>S^d</math> for any d ≥ 5. The proof is by reduction from the [[Word problem for groups|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>S^4</math>.<ref name=":0" />{{Rp|pages=11}}

== Manifold problem ==
The '''manifold problem''' is: given a finite simplicial complex, is it homeomorphic to a [[Manifold|manifold]]? The problem is undecidable; the proof is by reduction from the [[Word problem for groups|word problem for groups]].<ref name=":0" />{{Rp|pages=11}}

== References ==
{{reflist}}

[[Category:Simplicial sets]]

{{Sourceattribution|Simplicial complex recognition problem}}