Editing Computational topology (section)

===Algorithmic 3-manifold theory===

A large family of algorithms concerning [[3-manifold]]s 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 [[Triangulation (topology)|triangulated]] [[3-manifold]] and determines whether or not the manifold is [[homeomorphism|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.  Saul Schleimer went on to show the problem lies in the complexity class [[NP (complexity)|NP]].<ref>{{cite web |first=Saul |last=Schleimer |title=Sphere Recognition Lies in NP |url=http://www.warwick.ac.uk/~masgar/Maths/np.pdf |date=2011 |via=[[University of Warwick]]}}</ref>   Furthermore, Raphael Zentner showed that the problem lies in the complexity class coNP,<ref>{{cite journal |arxiv=1605.08530 |title=Integer homology 3-spheres admit irreducible representations in SL(2,C) |year=2018 |last1=Zentner |first1=Raphael |s2cid=119275434 |journal=[[Duke Mathematical Journal]] |volume=167 |issue=9 |pages=1643–1712 |doi=10.1215/00127094-2018-0004 }}</ref> provided that the generalized Riemann hypothesis holds. He uses instanton gauge theory, the geometrization theorem of 3-manifolds, and subsequent work of Greg Kuperberg <ref>{{cite journal |arxiv=1112.0845 |last1=Kuperberg |first1=Greg |s2cid=12634367 |title=Knottedness is in NP, modulo GRH |journal=[[Advances in Mathematics]] |year=2014 |volume=256 |pages=493–506 |doi=10.1016/j.aim.2014.01.007 |doi-access=free }}</ref> on the complexity of knottedness detection.
* The [[connected sum|connect-sum]] decomposition of 3-manifolds is also implemented in [[Regina (program)|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<ref>{{cite journal |arxiv=0909.4625 |last1=Burton |first1=Benjamin A. |last2=Hyam Rubinstein |first2=J. |last3=Tillmann |first3=Stephan |title=The Weber-Seifert dodecahedral space is non-Haken |year=2009 |journal=[[Transactions of the American Mathematical Society]] |volume=364 |number=2 |pages=911–932 |doi=10.1090/S0002-9947-2011-05419-X|s2cid=18435885 }}</ref> 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 for groups|word problem]].<ref>J.Manning, Algorithmic detection and description of hyperbolic structures on 3-manifolds with solvable word problem, Geometry and Topology 6 (2002) 1–26</ref>

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,<ref>S.Matveev, Algorithmic topology and the classification of 3-manifolds, Springer-Verlag 2003</ref> in fact, it is known that deciding whether two closed, oriented 3-manifolds given by [[Triangulation (topology)|triangulation]]s (simplicial complexes) are equivalent (homeomorphic) is [[elementary recursive]].<ref>{{cite journal | arxiv = 1508.06720| doi = 10.2140/pjm.2019.301.189| title = Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization| date = 2019| last1 = Kuperberg| first1 = Greg| journal = Pacific Journal of Mathematics| volume = 301| pages = 189–241| s2cid = 119298413}}</ref> This generalizes the result on 3-sphere recognition.

==== Conversion algorithms ====

* [[SnapPea]] implements an algorithm to convert a planar [[Knot (mathematics)|knot]] or [[Knot (mathematics)#knot diagram|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 theory|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.<ref>{{cite journal |doi=10.1112/jtopol/jtn017 |title=3-manifolds efficiently bound 4-manifolds |year=2008 |last1=Costantino |first1=Francesco |last2=Thurston |first2=Dylan |s2cid=15119190 |journal=[[Journal of Topology]] |volume=1 |issue=3 |pages=703–745 |arxiv=math/0506577 }}</ref>
* 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''.