A large family of algorithms concerning
3-manifolds revolve around
normal surface theory, which is a phrase that encompasses several techniques to turn problems in 3-manifold theory into integer linear programming problems.
Rubinstein and Thompson's 3-sphere recognition algorithm. This is an algorithm that takes as input a
triangulated3-manifold and determines whether or not the manifold is
homeomorphic to the
3-sphere. It has exponential run-time in the number of tetrahedral simplexes in the initial 3-manifold, and also an exponential memory profile. Moreover, it is implemented in the software package
Regina.[4] Saul Schleimer went on to show the problem lies in the complexity class
NP.[5] Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP,[6] provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg [7] on the complexity of knottedness detection.
The
connect-sum decomposition of 3-manifolds is also implemented in
Regina, has exponential run-time and is based on a similar algorithm to the 3-sphere recognition algorithm.
Determining that the Seifert-Weber 3-manifold contains no incompressible surface has been algorithmically implemented by Burton, Rubinstein and Tillmann[8] and based on normal surface theory.
The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose
fundamental group have a solution to the
word problem.[9]
At present the
JSJ decomposition has not been implemented algorithmically in computer software. Neither has the compression-body decomposition. There are some very popular and successful heuristics, such as
SnapPea which has much success computing approximate hyperbolic structures on triangulated 3-manifolds. It is known that the full classification of 3-manifolds can be done algorithmically,[10] in fact, it is known that deciding whether two closed, oriented 3-manifolds given by
triangulations (simplicial complexes) are equivalent (homeomorphic) is
elementary recursive.[11] This generalizes the result on 3-sphere recognition.
Conversion algorithms
SnapPea implements an algorithm to convert a planar
knot or
link diagram into a cusped triangulation. This algorithm has a roughly linear run-time in the number of crossings in the diagram, and low memory profile. The algorithm is similar to the Wirthinger algorithm for constructing presentations of the
fundamental group of link complements given by planar diagrams. Similarly, SnapPea can convert
surgery presentations of 3-manifolds into triangulations of the presented 3-manifold.
D. Thurston and F. Costantino have a procedure to construct a triangulated 4-manifold from a triangulated 3-manifold. Similarly, it can be used to construct surgery presentations of triangulated 3-manifolds, although the procedure is not explicitly written as an algorithm in principle it should have polynomial run-time in the number of tetrahedra of the given 3-manifold triangulation.[12]
S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in
Dehn twist generators) for the
mapping class group of a surface. The 3-manifold is the one that uses the word as the attaching map for a
Heegaard splitting of the 3-manifold. The algorithm is based on the concept of a layered triangulation.
Given two (tame) knots by link diagrams deciding whether they are equivalent is
ER. This is established by reducing knot equivalence (
isotopy) to equivalence (
homeomorphy) of the associated
knot complements which are
3-manifolds which in turn can be encoded by
triangulations. Since these knot complements are
Haken manifolds one then uses a result that the equivalence problem of these manifolds is in ER. There does not seem to be a good reference for this, these results are scattered across the literature in the field, but well-known by the community.
Brown has an algorithm to compute the homotopy groups of spaces that are finite
Postnikov complexes,[19] although it is not widely considered implementable.
Computational homology
Computation of
homology groups of
cell complexes reduces to bringing the boundary matrices into
Smith normal form. Although this is a completely solved problem algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has cubic complexity in the size of the matrix involved since it uses row and column operations which makes it unsuitable for large cell complexes. Secondly, the intermediate matrices which result from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices.
Efficient and probabilistic Smith normal form algorithms, as found in the
LinBox library.
Simple homotopic reductions for pre-processing homology computations, as in the
Perseus software package.
^Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences, Cham: Springer International Publishing, pp. 1–23,
doi:
10.1007/978-3-319-70658-0_87-1,
ISBN978-3-319-70658-0,
S2CID226695484
^J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
^S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
^Przytycki, Jozef H. (2017). "The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming".
arXiv:1707.07733 [
math.GT].
^Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial".
arXiv:quant-ph/0511096.
A large family of algorithms concerning
3-manifolds revolve around
normal surface theory, which is a phrase that encompasses several techniques to turn problems in 3-manifold theory into integer linear programming problems.
Rubinstein and Thompson's 3-sphere recognition algorithm. This is an algorithm that takes as input a
triangulated3-manifold and determines whether or not the manifold is
homeomorphic to the
3-sphere. It has exponential run-time in the number of tetrahedral simplexes in the initial 3-manifold, and also an exponential memory profile. Moreover, it is implemented in the software package
Regina.[4] Saul Schleimer went on to show the problem lies in the complexity class
NP.[5] Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP,[6] provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg [7] on the complexity of knottedness detection.
The
connect-sum decomposition of 3-manifolds is also implemented in
Regina, has exponential run-time and is based on a similar algorithm to the 3-sphere recognition algorithm.
Determining that the Seifert-Weber 3-manifold contains no incompressible surface has been algorithmically implemented by Burton, Rubinstein and Tillmann[8] and based on normal surface theory.
The Manning algorithm is an algorithm to find hyperbolic structures on 3-manifolds whose
fundamental group have a solution to the
word problem.[9]
At present the
JSJ decomposition has not been implemented algorithmically in computer software. Neither has the compression-body decomposition. There are some very popular and successful heuristics, such as
SnapPea which has much success computing approximate hyperbolic structures on triangulated 3-manifolds. It is known that the full classification of 3-manifolds can be done algorithmically,[10] in fact, it is known that deciding whether two closed, oriented 3-manifolds given by
triangulations (simplicial complexes) are equivalent (homeomorphic) is
elementary recursive.[11] This generalizes the result on 3-sphere recognition.
Conversion algorithms
SnapPea implements an algorithm to convert a planar
knot or
link diagram into a cusped triangulation. This algorithm has a roughly linear run-time in the number of crossings in the diagram, and low memory profile. The algorithm is similar to the Wirthinger algorithm for constructing presentations of the
fundamental group of link complements given by planar diagrams. Similarly, SnapPea can convert
surgery presentations of 3-manifolds into triangulations of the presented 3-manifold.
D. Thurston and F. Costantino have a procedure to construct a triangulated 4-manifold from a triangulated 3-manifold. Similarly, it can be used to construct surgery presentations of triangulated 3-manifolds, although the procedure is not explicitly written as an algorithm in principle it should have polynomial run-time in the number of tetrahedra of the given 3-manifold triangulation.[12]
S. Schleimer has an algorithm which produces a triangulated 3-manifold, given input a word (in
Dehn twist generators) for the
mapping class group of a surface. The 3-manifold is the one that uses the word as the attaching map for a
Heegaard splitting of the 3-manifold. The algorithm is based on the concept of a layered triangulation.
Given two (tame) knots by link diagrams deciding whether they are equivalent is
ER. This is established by reducing knot equivalence (
isotopy) to equivalence (
homeomorphy) of the associated
knot complements which are
3-manifolds which in turn can be encoded by
triangulations. Since these knot complements are
Haken manifolds one then uses a result that the equivalence problem of these manifolds is in ER. There does not seem to be a good reference for this, these results are scattered across the literature in the field, but well-known by the community.
Brown has an algorithm to compute the homotopy groups of spaces that are finite
Postnikov complexes,[19] although it is not widely considered implementable.
Computational homology
Computation of
homology groups of
cell complexes reduces to bringing the boundary matrices into
Smith normal form. Although this is a completely solved problem algorithmically, there are various technical obstacles to efficient computation for large complexes. There are two central obstacles. Firstly, the basic Smith form algorithm has cubic complexity in the size of the matrix involved since it uses row and column operations which makes it unsuitable for large cell complexes. Secondly, the intermediate matrices which result from the application of the Smith form algorithm get filled-in even if one starts and ends with sparse matrices.
Efficient and probabilistic Smith normal form algorithms, as found in the
LinBox library.
Simple homotopic reductions for pre-processing homology computations, as in the
Perseus software package.
^Blevins, Ann Sizemore; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), "Topology in Biology", Handbook of the Mathematics of the Arts and Sciences, Cham: Springer International Publishing, pp. 1–23,
doi:
10.1007/978-3-319-70658-0_87-1,
ISBN978-3-319-70658-0,
S2CID226695484
^J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26
^S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003
^Przytycki, Jozef H. (2017). "The first coefficient of Homflypt and Kauffman polynomials: Vertigan proof of polynomial complexity using dynamic programming".
arXiv:1707.07733 [
math.GT].
^Aharonov, Dorit; Jones, Vaughan; Landau, Zeph (2005). "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial".
arXiv:quant-ph/0511096.