A new algorithm for recognizing the unknot

DOI10.2140/GT.1998.2.175MaRDI QIDQ1279535zbMATH OpenOpenAlexWikidataFDO

Authors Joan Birman, M. Hirsch

Publication date 7 February 1999

Published in Geometry \& Topology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9801126, https://eudml.org/doc/120801, http://www.emis.de/journals/UW/gt/

zbMATH Keywords

braidfoliationknot

Mathematics Subject Classification ID

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

Abstract: The topological underpinnings are presented for a new algorithm which answers the question: `Is a given knot the unknot?' The algorithm uses the braid foliation technology of Bennequin and of Birman and Menasco. The approach is to consider the knot as a closed braid, and to use the fact that a knot is unknotted if and only if it is the boundary of a disc with a combinatorial foliation. The main problems which are solved in this paper are: how to systematically enumerate combinatorial braid foliations of a disc; how to verify whether a combinatorial foliation can be realized by an embedded disc; how to find a word in the the braid group whose conjugacy class represents the boundary of the embedded disc; how to check whether the given knot is isotopic to one of the enumerated examples; and finally, how to know when we can stop checking and be sure that our example is not the unknot.

Review text

A new algorithm for unknottedness is given. This is based on the braid foliation technology of \textit{D. Bennequin} [Astérisque 107/108, 87-161 (1983; Zbl 0573.58022)] and of \textit{J. S. Birman} and \textit{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, \textit{J. Hass, J. Lagarias} and \textit{N. Pippenger} have shown that the problem is in the class NP [The computational complexity of knot and links problems, preprint 1997].

Recommendations

• scientific article; zbMATH DE number 1303213
• TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT
• Recognition algorithms in knot theory
• Algorithms for recognizing knots and 3-manifolds
• scientific article; zbMATH DE number 1860721
• Visual Algebraic Proofs for Unknot Detection
• An efficient algorithm to decide the knot problem
• Recognizing Knots Using Simulated Annealing
• On the unknotting problem
• Algorithmic simplification of knot diagrams: new moves and experiments

Cites work

• A new approach to the word and conjugacy problems in the braid groups
• ALGORITHMS FOR POSITIVE BRAIDS
• Algorithms for recognizing knots and 3-manifolds
• Band-generator presentation for the 4-braid group
• scientific article; zbMATH DE number 3915280 (Why is no real title available?)
• On the computational complexity of the Jones and Tutte polynomials
• Representation of links by braids: A new algorithm
• Studying Links Via Closed Braids. V: The Unlink
• STUDYING SURFACES VIA CLOSED BRAIDS
• THE BRAID GROUP AND OTHER GROUPS
• The computational complexity of knot and link problems
• THE GENUS OF CLOSED 3-BRAIDS
• The minimal number of Seifert circles equals the braid index of a link
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten

Cited in

(22)

• Obstructions to trivializing a knot
• Notes on tiled incompressible tori
• Untangling the Newman-Janis algorithm
• Braid ordering and the geometry of closed braid
• Diagram invariants of knots and the Kontsevich integral
• Stabilization in the braid groups. I: MTWS
• Open book foliation
• The number of Reidemeister moves needed for unknotting
• The Unknotting Problem
• Algorithmic simplification of knot diagrams: new moves and experiments
• Post quantum cryptography from mutant prime knots
• Braid ordering and knot genus
• On the unknotting problem
• TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT
• scientific article; zbMATH DE number 1860721 (Why is no real title available?)
• Recognition algorithms in knot theory
• Rectangular knot diagrams classification with deep learning
• Arc-presentations of links: Monotonic simplification
• AN EASY AND FAST ALGORITHM FOR OBTAINING MINIMAL DISCRETE KNOTS
• Detecting Unknots via Equational Reasoning, I: Exploration
• Visual Algebraic Proofs for Unknot Detection
• A quantitative Birman–Menasco finiteness theorem and its application to crossing number

This page was built for publication: A new algorithm for recognizing the unknot

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1279535)