DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2019.49

The Unbearable Hardness of Unknotting

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

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract

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

Cite as

Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, and Martin Tancer. The Unbearable Hardness of Unknotting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{demesmay_et_al:LIPIcs.SoCG.2019.49,
  author =	{de Mesmay, Arnaud and Rieck, Yo'av and Sedgwick, Eric and Tancer, Martin},
  title =	{{The Unbearable Hardness of Unknotting}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.49},
  URN =		{urn:nbn:de:0030-drops-104530},
  doi =		{10.4230/LIPIcs.SoCG.2019.49},
  annote =	{Keywords: Knot, Link, NP-hard, Reidemeister move, Unknot recognition, Unlinking number, intermediate invariants}
}

Search Results

Documents authored by Sedgwick, Eric

The Unbearable Hardness of Unknotting

Abstract

Cite as

Thanks for your feedback!

Could not send message