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

knotlinkNP-hardReidemeister moveunknot recognitionunlinking number

Mathematics Subject Classification ID

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

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

Review text

Let \(D\) be a knot diagram of the unknot, and \(k\) an integer. The problem of determining if \(D\) can be untangled using at most \(k\) Reidemeister moves is known to be in NP. The authors of the present article show that the problem is actually NP-complete. This is done by providing a polynomial time algorithm that reduces the Boolean 3-satisfiability problem to an unkotting problem. Using similar techniques, it is also established that the problem of determining if a link diagram \(L\) has a sublink that is an unlink with \(k\) components is NP-hard. Moreover, determining whether certain link invariants of \(L\), such as the unlinking number, take on the value \(k\) is shown to be NP-hard as well.

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

• 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
• 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?)
• 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

(17)

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

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)