2018/10/08 by de Mesmay, Arnaud, Rieck, Yo'av, Sedgwick, Eric +1 · 1 citation
#FOS: Mathematics #Geometric Topology (math.GT)
paper · doi:10.48550/arxiv.1810.03502
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).