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

Birman, Joan S.; Hirsch, Michael D.

Geom. Topol. 2, 175-220 (1998).

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].

Reviewer: Christian Blanchet (Vannes)

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

Citations:

Zbl 0573.58022; Zbl 0758.57005

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 · doi:10.1142/S0218216598000176
[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 · doi:10.1006/aima.1998.1761
[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 · doi:10.2307/2153953
[6]	E A El-Rifai, H R Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. \((2)\) 45 (1994) 479 · Zbl 0839.20051 · doi:10.1093/qmath/45.4.479
[7]	F A Garside, The braid group and other groups, Quart. J. Math. Oxford Ser. \((2)\) 20 (1969) 235 · Zbl 0194.03303 · doi:10.1093/qmath/20.1.235
[8]	W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245 · Zbl 0100.19402 · doi:10.1007/BF02559591
[9]	J Hass, Algorithms for recognizing knots and 3-manifolds, Chaos Solitons Fractals 9 (1998) 569 · Zbl 0935.57014 · doi:10.1016/S0960-0779(97)00109-4
[10]	J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185 · Zbl 1065.68667 · doi:10.1145/301970.301971
[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 · doi:10.1017/S0305004100068936
[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 · doi:10.1016/S0166-8641(96)00148-4
[13]	P Vogel, Representation of links by braids: a new algorithm, Comment. Math. Helv. 65 (1990) 104 · Zbl 0703.57004 · doi:10.1007/BF02566597
[14]	P Xu, The genus of closed 3-braids, J. Knot Theory Ramifications 1 (1992) 303 · Zbl 0773.57007 · doi:10.1142/S0218216592000185
[15]	S Yamada, The minimal number of Seifert circles equals the braid index of a link, Invent. Math. 89 (1987) 347 · Zbl 0634.57004 · doi:10.1007/BF01389082