Simplicial complex recognition problem

<h2 id="background">Background</h2>
<p>An <a href="/facts/Abstract_simplicial_complex/ytwxClsf">abstract simplicial complex</a> (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 <a href="/facts/Geometric_simplicial_complex/fF2282CF">geometric simplicial complex</a> (GSC), where each set with <i>k</i> elements in the ASC is mapped to a (<i>k</i>-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.
</p>
<h2 id="homeomorphism-problem">Homeomorphism problem</h2>
<p>The homeomorphism problem is: given two finite simplicial complexes representing <a href="/facts/Smooth_manifolds/aSnbXKcV">smooth manifolds</a>, decide if they are <a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">homeomorphic</a>.
</p>
<ul><li>If the complexes are of dimension at most 3, then the problem is decidable. This follows from the proof of the <a href="/facts/Geometrization_conjecture/FDpqIM7y">geometrization conjecture</a>.</li>
<li>For every d ≥ 4, the homeomorphism problem for <i>d</i>-dimensional simplicial complexes is undecidable.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>
<p>The same is true if "homeomorphic" is replaced with "<a href="/facts/Piecewise_linear_homeomorphism/dq3fTkPT">piecewise-linear homeomorphic</a>".
</p>
<h2 id="recognition-problem">Recognition problem</h2>
<p>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.
</p>
<ul><li>The recognition problem is decidable for the 3-dimensional sphere 
  
    
      
        
          S
          
            3
          
        
      
    
    {\displaystyle S^{3}}
  
.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> That is, there is an algorithm that can decide whether any given simplicial complex is homeomorphic to the boundary of a 4-dimensional ball.</li>
<li>The recognition problem is undecidable for the d-dimensional sphere 
  
    
      
        
          S
          
            d
          
        
      
    
    {\displaystyle S^{d}}
  
 for any d ≥ 5. The proof is by reduction from the <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem for groups</a>. From this, it can be proved that the recognition problem is undecidable for any fixed compact <i>d</i>-dimensional manifold with d ≥ 5.</li>
<li>As of 2014, it is open whether the recognition problem is decidable for the 4-dimensional sphere 
  
    
      
        
          S
          
            4
          
        
      
    
    {\displaystyle S^{4}}
  
.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>: 11 </li></ul>
<h2 id="manifold-problem">Manifold problem</h2>
<p>The manifold problem is: given a finite simplicial complex, is it homeomorphic to a <a href="/facts/Manifold/rXPERJtu">manifold</a>? The problem is undecidable; the proof is by reduction from the <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem for groups</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>: 11 
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72, Springer, p. 247, ISBN 9780387979700. <a href="9780387979700" target="_blank">9780387979700</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Poonen, Bjorn (2014-10-25). "Undecidable problems: a sampler". arXiv:1204.0299 [math.LO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>"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. <a href="https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=23250&option_lang=eng" target="_blank">https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=23250&option_lang=eng</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Matveev, Sergei (2003), Matveev, Sergei (ed.), "Algorithmic Recognition of S3", Algorithmic Topology and Classification of 3-Manifolds, Algorithms and Computation in Mathematics, vol. 9, Berlin, Heidelberg: Springer, pp. 193–214, doi:10.1007/978-3-662-05102-3_5, ISBN 978-3-662-05102-3, retrieved 2022-11-27 <a href="978-3-662-05102-3" target="_blank">978-3-662-05102-3</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Poonen, Bjorn (2014-10-25). "Undecidable problems: a sampler". arXiv:1204.0299 [math.LO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Poonen, Bjorn (2014-10-25). "Undecidable problems: a sampler". arXiv:1204.0299 [math.LO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Simplicial complex recognition problem open-in-new

Simplicial complex recognition problem