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.

Background

An abstract simplicial complex is family of sets that is closed under taking subsets. Every abstract simplicial complex has a unique geometric realization in a Euclidean space as a geometric simplicial complex, where each set with k elements in the ASC is mapped to a -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.
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. 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 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.

    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.