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.

This publication has 14 references indexed in Scilit: