Importance: High ✭✭✭
 Author(s): Novikov
 Subject: Topology
 Keywords: 4-sphere algorithm
 Recomm. for undergrads: no
 Posted by: rybu on: November 7th, 2009
Problem   Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?

A 4-manifold triangulation admits a unique smoothing up to diffeomorphism, so this problem is equivalent to asking for an algorithm to determine if a 4-manifold is diffeomorphic to the 4-sphere (with standard differentiable structure). "Combinatorial equivalence" refers to the ability to pass from one triangulation to another via a sequence of Pachner moves.

Rubinstein has an algorithm to determine if a triangulated 3-manifold is combinatorially equivalent to the 3-sphere. A consequence of his algorithm is that there is an algorithm to determine if a 4-dimensional simplicial complex is a 4-manifold triangulation.

It's known that no algorithms exist to determine if a triangulated 4-manifold has a trivial fundamental group, as there is a procedure to construct a compact 4-manifold with any finitely presented fundamental group.

In dimensions 5 and higher, Novikov proved that there is no algorithm to decide whether a given triangulated -manifold is combinatorially equivalent to the -sphere is undecidable [N, CL]. Also, it is undecidable whether a given triangulated 4-manifold is combinatorially equivalent to a connect sum of 14 copies of .

## Bibliography

[CL] Chernavsky, A. V, and Leskine, V. P., Unrecognizability of manifolds, Annals of Pure and Applied Logic 141 (2006) 325--335.

[N] Novikov, P.S., On the algorithSSSR 85 (5) (19552) 709--712 (in Russian). Algorithmic unsolvability of the problem of identity, Dokl. Akad. Nauk SSSR 85 (5) (1952) 709--712 (in Russian).

[T] Thompson, A. Thin position and the recognition problem for . MRL (1994).

* indicates original appearance(s) of problem.