×

A new algorithm for recognizing the unknot. (English) Zbl 0955.57005

A new algorithm for unknottedness is given. This is based on the braid foliation technology of D. Bennequin [Astérisque 107/108, 87-161 (1983; Zbl 0573.58022)] and of J. S. Birman and W. W. Menasco [Trans. Am. Math. Soc. 329, No. 2, 585-606 (1992; Zbl 0758.57005)].
The given knot is written as the closure of a braid. The algorithm will enumerate a finite list of closed braids containing examples from each conjugacy class representing the unknot, with bounded complexity. The given knot is unknotted if and only if it is in the conjugacy class of a braid in the list.
Haken’s work already proved the existence of an algorithm for recognizing the unknot. By sharpening Haken’s method, J. Hass, J. Lagarias and N. Pippenger have shown that the problem is in the class NP [The computational complexity of knot and links problems, preprint 1997].

MSC:

57M25 Knots and links in the \(3\)-sphere (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
57M50 General geometric structures on low-dimensional manifolds
57M15 Relations of low-dimensional topology with graph theory
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

knot; braid; foliation
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML EMIS

References:

[1] D Bennequin, Entrelacements et équations de Pfaff, Astérisque 107, Soc. Math. France (1983) 87 · Zbl 0573.58022
[2] J S Birman, Braids, links, and mapping class groups, Annals of Mathematics Studies 82, Princeton University Press (1974)
[3] J S Birman, E Finkelstein, Studying surfaces via closed braids, J. Knot Theory Ramifications 7 (1998) 267 · Zbl 0907.57006
[4] J Birman, K H Ko, S J Lee, A new approach to the word and conjugacy problems in the braid groups, Adv. Math. 139 (1998) 322 · Zbl 0937.20016
[5] J S Birman, W W Menasco, Studying links via closed braids V: The unlink, Trans. Amer. Math. Soc. 329 (1992) 585 · Zbl 0758.57005
[6] E A El-Rifai, H R Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. \((2)\) 45 (1994) 479 · Zbl 0839.20051
[7] F A Garside, The braid group and other groups, Quart. J. Math. Oxford Ser. \((2)\) 20 (1969) 235 · Zbl 0194.03303
[8] W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245 · Zbl 0100.19402
[9] J Hass, Algorithms for recognizing knots and 3-manifolds, Chaos Solitons Fractals 9 (1998) 569 · Zbl 0935.57014
[10] J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185 · Zbl 1065.68667
[11] F Jaeger, D L Vertigan, D J A Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990) 35 · Zbl 0747.57006
[12] E S Kang, K H Ko, S J Lee, Band-generator presentation for the 4-braid group, Topology Appl. 78 (1997) 39 · Zbl 0879.57005
[13] P Vogel, Representation of links by braids: a new algorithm, Comment. Math. Helv. 65 (1990) 104 · Zbl 0703.57004
[14] P Xu, The genus of closed 3-braids, J. Knot Theory Ramifications 1 (1992) 303 · Zbl 0773.57007
[15] S Yamada, The minimal number of Seifert circles equals the braid index of a link, Invent. Math. 89 (1987) 347 · Zbl 0634.57004
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.