×
Hass, Joel

Algorithms for recognizing knots and 3-manifolds. (English) Zbl 0935.57014

Chaos Solitons Fractals 9, No. 4-5, 569-581 (1998).
In this survey paper the author describes some topological and algebraic algorithms for recognizing knots and 3-manifolds; in particular, those that relate to distinguishing knots. Algorithms are of interest to geometric topologists for two reasons. First, they have a bearing on the decidability of a problem. Secondly, the discovery of a reasonably efficient algorithm can lead to a computer program which can be used to examine interesting examples. In this paper, one can find various algorithms to recognize the unknot.
Reviewer: A.Cavicchioli (Modena)

Cited in 2 Reviews
Cited in 10 Documents

MSC:

57M25 Knots and links in the \(3\)-sphere (MSC2010)
57N10 Topology of general \(3\)-manifolds (MSC2010)

Keywords:

Haken manifold; normal surface
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[2] Rotman, J. J., The Theory of Groups (1973), Allyn & Bacon: Allyn & Bacon Boston, MA · Zbl 0262.20001
[3] Markov, A. A., Insolubility of a problem of homeomorphy, (Proceedings of an International Congress of Mathematicians (1958), Cambridge University Press), 300-306 · Zbl 0092.00702
[4] Moise, E. E., Affine Structures in 3-manifolds V, Ann. Math., 55, 96-114 (1952) · Zbl 0048.17102
[5] Meeks, W. H.; Yau, S. T., Topology of three dimensional manifolds and the embedding theorems in minimal surface theory, Ann. Math., 112, 441-484 (1980) · Zbl 0458.57007
[6] Meeks, W.; Simon, L.; Yau, S. T., Embedded minimal surfaces, exotic spheres and manifolds of positive Ricci curvature, Ann. Math., 116, 621-659 (1982) · Zbl 0521.53007
[7] Thurston, W., The geometry and topology of 3-dimensional manifolds, Princeton University Lecture Notes (1978)
[8] Kneser, H., Geschlossene Flachen in dreidimesionalen Mannifgfaltigkeiten, Jber. Ent. Math., Ver., 28, 248-260 (1929) · JFM 55.0311.03
[9] Papakyriakopoulous, C. D., On Dehn’s lemma and the asphericity of knots, Ann. Math., 66, 1-26 (1957) · Zbl 0078.16402
[10] Hempel, J., 3-manifolds, Ann. Math. Stud., 86 (1976) · Zbl 0345.57001
[11] Haken, W., Connections between topological and group theoretical decision problems, (Boone, W. W., Word Problems (1973), North Holland: North Holland Amsterdam), 427-441 · Zbl 0265.02033
[12] Haken, W., Theorie der Normalflachen, Acta Math., 105, 245-375 (1961) · Zbl 0100.19402
[13] Schubert, H., Bestimmung der Primfaktorzerlegung von Verkettungen, Math. Z., 76, 116-148 (1961) · Zbl 0097.16302
[14] Jaco, W.; Oertel, U., An algorithm to decide if a 3-manifold is a Haken manifold, Topology, 23, 2, 195-209 (1984) · Zbl 0545.57003
[15] Jaco, W.; Tollefson, J. L., Algorithms for the complete decomposition of a closed 3-manifold, Illinois J. Math., 39, 358-406 (1995) · Zbl 0858.57018
[16] Jaco, W.; Rubinstein, J. H., A piecewise linear theory of minimal surfaces in 3-manifolds, J. Diff. Geom., 27, 493-524 (1988) · Zbl 0652.57005
[17] Hempel, J., Residual finiteness for 3-manifolds, Combinatorial group theory and topology, Ann. Math. Stud., 111, 379-396 (1987) · Zbl 0772.57002
[18] Hemion, G., The Classification of Knots and 3-dimensional Spaces (1992), Oxford University Press · Zbl 0771.57001
[19] Rubinstein, J. H., Polyhedral minimal surfaces, Heegaard splittings and decision problems for 3-dimensional manifolds, (Proceedings of the Georgia Topology Conference (1993), Am. Math. Soc./Intl Press), 1-20 · Zbl 0889.57021
[20] Rubinstein, J. H., An algorithm to recognize the 3-sphere, (Proceedings of the ICM. Proceedings of the ICM, Zurich (1994)), 3, To appear in
[21] Thompson, A., Thin position and the recognition problem for \(S^3\), Math. Res. Lett., 1, 613-630 (1994) · Zbl 0849.57009
[22] Stocking, M., Almost normal surfaces in 3-manifolds, (Ph.D. Thesis (1996), UC Davis) · Zbl 0933.57016
[23] Sela, Z., The isomorphism problem for hyperbolic groups I, Ann. Math., 141, 217-283 (1995) · Zbl 0868.57005
[24] Johannson, K., Classification problems in low-dimensional topology, (Geometric and Algebraic Topology (1986), Banach Center Publ. 18. PWN: Banach Center Publ. 18. PWN Warsaw), 37-59 · Zbl 0639.57001
[25] Matveev, S. V., Algorithms for the recognition of the three-dimensional sphere (after A. Thompson), Mat. Sb., 186, 69-84 (1995) · Zbl 0849.57010
[26] Waldhausen, F., Recent results on sufficiently large 3-manifolds, (Proceedings of the Symposium in Pure Mathematics, Vol. 32 (1978), Am. Math. Soc.), 21-38 · Zbl 0391.57011
[27] Waldhausen, F., Some problems on 3-manifolds, (Proceedings of the Symposium in Pure Mathematics, Vol. 32 (1978), Am. Math. Soc.), 313-322 · Zbl 0397.57007
[28] Birman, J.; Hirsch, M. D., Recognizing the unknot (1997), Preprint
[29] Hass, J.; Lagarias, J. C.; Pippenger, N., The computational complexity of knot and link problems, (Proc. 38th Annual Symposium On Foundations of Computer Science (1997)), 172-181
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.