NP–hard problems naturally arising in knot theory
Open Access
- 27 May 2021
- journal article
- research article
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society, Series B
- Vol. 8 (15) , 420-441
Abstract
We prove that certain problems naturally arising in knot theory are NP–hard or NP–complete. These are the problems of obtaining one diagram from another one of a link in a bounded number of Reidemeister moves, determining whether a link has an unlinking or splitting number k k , finding a k k -component unlink as a sublink, and finding a k k -component alternating sublink.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Some Conditionally Hard Problems on Links and 3-ManifoldsDiscrete & Computational Geometry, 2017
- Elementary Knot Theory2017
- A polynomial upper bound on Reidemeister movesAnnals of Mathematics, 2015
- An upper bound on Reidemeister movesAmerican Journal of Mathematics, 2014
- Unknotting genus one knotsCommentarii Mathematici Helvetici, 2011
- Knots and Links2003
- The computational complexity of knot and link problemsJournal of the ACM, 1999
- Closed incompressible surfaces in alternating knot and link complementsTopology, 1984
- The Planar Hamiltonian Circuit Problem is NP-CompleteSIAM Journal on Computing, 1976
- Knoten und GruppenAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1927