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. 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. Algorithmic knot theory Determining whether or not a knot is trivial is known to be in the complexity class NP The problem of determining the genus of a knot is known to have complexity class PSPACE. There are polynomial-time algorithms for the computation of the Alexander polynomial of a knot. Computational homotopy Computational methods for homotopy groups of spheres. Computational methods for solving systems of polynomial equations. Brown has an algorithm to compute the homotopy groups of spaces that are finite Postnikov complexes, 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. Algorithms to compute persistent homology of filtered complexes, as in the TDAstats R package. See also Computable topology (the study of the topological nature of computation) Computational geometry Digital topology Topological data analysis Spatial-temporal reasoning Experimental mathematics Geometric modeling References External links CompuTop software archive Workshop on Application of Topology in Science and Engineering Computational Topology at Stanford