2026-07-23T08:46:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10453 2024-03-06T10:46:01Z ddc:004 open_access

The Unbearable Hardness of Unknotting de Mesmay, Arnaud Rieck, Yo'av Sedgwick, Eric Tancer, Martin Knot Link NP-hard Reidemeister move Unknot recognition Unlinking number intermediate invariants We prove that deciding if a diagram of the unknot can be untangled using at most k Reidemeister 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnaud de Mesmay and Yo'av Rieck and Eric Sedgwick and Martin Tancer 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.49 urn:nbn:de:0030-drops-104530 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.49 eng https://creativecommons.org/licenses/by/3.0/legalcode