The unbearable hardness of unknotting

DOI10.1016/j.aim.2021.107648zbMath1484.57003arXiv1810.03502OpenAlexW2963094264MaRDI QIDQ2656151

Eric Sedgwick, Martin Tancer, Arnaud de Mesmay, Yo'av Rieck

Publication date: 10 March 2021

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.03502

zbMATH Keywords

knotlinkNP-hardunlinking numberReidemeister moveunknot recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knot theory (57K10)

Related Items

Computing a link diagram from its exterior, NP–hard problems naturally arising in knot theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial upper bound on Reidemeister moves
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle
• Homology of group systems with applications to knot theory
• Some relations among various numerical invariants for links
• Untangling planar curves
• Computational complexity and 3-manifolds and zombies
• Some conditionally hard problems on links and 3-manifolds
• Knottedness is in NP, modulo GRH
• The number of Reidemeister moves needed for unknotting
• Slicing mixed Bing-Whitehead doubles
• The computational complexity of knot and link problems
• Embeddability in $\mathbb{R}^3$ is NP-hard
• Elementary knot theory
• Computational Complexity
• The computational complexity of knot genus and spanning area
• On a Certain Numerical Invariant of Link Types