文章基本信息

标题：The Unbearable Hardness of Unknotting
本地全文：下载
作者：Arnaud de Mesmay ; Yo'av Rieck ; Eric Sedgwick 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-19
DOI：10.4230/LIPIcs.SoCG.2019.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：Knot; Link; NP-hard; Reidemeister move; Unknot recognition; Unlinking number; intermediate invariants