The unbearable hardness of unknotting

DOI10.1016/J.AIM.2021.107648zbMATH Open1484.57003arXiv1810.03502OpenAlexW2963094264MaRDI QIDQ2656151FDOQ2656151

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)

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

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

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

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)

Cites Work

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

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)