The unbearable hardness of unknotting (Q2656151)

Let \(D\) be a knot diagram of the unknot, and \(k\) an integer. The problem of determining if \(D\) can be untangled using at most \(k\) Reidemeister moves is known to be in NP. The authors of the present article show that the problem is actually NP-complete. This is done by providing a polynomial time algorithm that reduces the Boolean 3-satisfiability problem to an unkotting problem. Using similar techniques, it is also established that the problem of determining if a link diagram \(L\) has a sublink that is an unlink with \(k\) components is NP-hard. Moreover, determining whether certain link invariants of \(L\), such as the unlinking number, take on the value \(k\) is shown to be NP-hard as well.