The unbearable hardness of unknotting

DOI10.1016/J.AIM.2021.107648MaRDI QIDQ2656151zbMATH OpenOpenAlexFDO

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

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, https://drops.dagstuhl.de/opus/volltexte/2019/10453/

zbMATH Keywords

NP-hardknotlinkunlinking 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)

Abstract: We prove that deciding if a diagram of the unknot can be untangled using at most $k$ Riedemeister moves (where $k$ is part of the input) is NP-hard. We also prove that several natural questions regarding links in the $3$-sphere are NP-hard, including detecting whether a link contains a trivial sublink with $n$ components, computing the unlinking number of a link, and computing a variety of link invariants related to four-dimensional topology (such as the $4$-ball Euler characteristic, the slicing number, and the $4$-dimensional clasp number).

Recommendations

• NP-hard problems naturally arising in knot theory
• A polynomial upper bound on Reidemeister moves
• The computational complexity of knot and link problems
• Unknotting is in \(\mathsf{AM} \cap \mathsf{co-AM}\)
• On a problem of effective knot theory

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 638756 (Why is no real title available?)
• scientific article; zbMATH DE number 732196 (Why is no real title available?)
• scientific article; zbMATH DE number 732197 (Why is no real title available?)
• scientific article; zbMATH DE number 877622 (Why is no real title available?)
• A polynomial upper bound on Reidemeister moves
• Computational Complexity
• Computational complexity and 3-manifolds and zombies
• Elementary knot theory
• Embeddability in \(\mathbb R^3\) is NP-hard
• Hard unknots and collapsing tangles
• Homology of group systems with applications to knot theory
• Knottedness is in NP, modulo GRH
• On a Certain Numerical Invariant of Link Types
• Slicing mixed Bing-Whitehead doubles
• Some conditionally hard problems on links and 3-manifolds
• Some relations among various numerical invariants for links
• The computational complexity of knot and link problems
• The computational complexity of knot genus and spanning area
• The number of Reidemeister moves needed for unknotting
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle
• Untangling planar curves

Cited in

(12)

• Computing a link diagram from its exterior
• Linkless and flat embeddings in 3-space and the unknot problem
• Link crossing number is NP-hard
• On the unknotting problem
• NP-hard problems naturally arising in knot theory
• The word problem for braided monoidal categories is unknot-hard
• Hard Diagrams of the Unknot
• The Unknotting Problem
• Knots, Reidemeister moves, and algorithms [after Lackenby]
• Complexity of unknotting of trivial \(2\)-knots
• Unknotting is in \(\mathsf{AM} \cap \mathsf{co-AM}\)
• Some conditionally hard problems on links and 3-manifolds

This page was built for publication: The unbearable hardness of unknotting

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