# NP–hard problems naturally arising in knot theory

## 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 finding a , unlink as a sublink, and finding a -component alternating sublink. -component

## 1. Overview

Many problems that lie at the heart of classical knot theory can be formulated as decision problems, with an algorithm being a solution. Among them, for example, is the question of equivalence (up to isotopy) of two links given by their diagrams. This can be approached in many different ways, among which applying Reidemeister moves perhaps has the longest history. Other examples are the unknotting, unlinking and splitting number questions, i.e. arriving to a diagram of an unlink, an unknot, or a split diagram from some diagram by interchanging overpasses and underpasses in a certain number of crossings.

The complexities of these basic decision problems in knot theory are not yet well-understood. Despite the lack of polynomial algorithms, few problems in knot theory are known to be NP–hard or NP–complete at all. Those few problems are the problem of determining a bound on the genus of a knot in a general 3-manifold Reference 1 improved to knots in in Reference 14, the problem of detecting a sublink isotopic to a given link, and the problem of determining a bound for the Thurston complexity of a link Reference 14. The purpose of this paper to establish that a number of other natural problems in knot theory are NP–hard. The problems described here have a advantage that they can be formulated solely in terms of link diagrams. They are described below. For an overview of complexity theory including NP–hardness and NP–completeness, see, for example, Reference 5. The status of many decision and complexity problems from knot theory is discussed in Reference 11.

In section 2 we look at the unlink as a sublink problem, a special case of the sublink problem defined and proven to be NP–hard by Lackenby Reference 14. We prove that the unlink as a sublink problem is NP–hard. Note that restricting a problem makes it easier, so the proof that the restricted problem is hard also implies that the general problem is hard. Thus, NP–hardness of the sublink problem is a corollary of the NP–hardness of the problem that we consider. The techniques used in the proof are widely used throughout this paper. More generally, for any property of links one can also consider decision problems of the form “Given a diagram of a link L and a positive integer k, is there a k component sublink of with the property We show in section ?”5 that this is also NP–hard if is the property of being an alternating link. We expect that many other problems of this form are NP–hard.

Very little is known about unknotting, unlinking and splitting numbers in general, without restricting to particular classes of links. It is possible that these invariants are not even computable. Moreover, it is not known whether there is an algorithm to detect whether a knot has unknotting number 1. A recent breakthrough by Lackenby suggests an algorithm to determine whether a hyperbolic link satisfying certain restrictions has unlinking or splitting number one Reference 15, but no algorithm for the general case is yet known. We provide the first lower bounds on the complexities of the general unlinking and splitting number problems in sections 3 and 4.

Reidemeister showed that any two diagrams of the same link can be taken one to another by a sequence of Reidemeister moves Reference 17. The bounds for the number of moves have been a long-standing question, and increasingly good results have been obtained for a general case, as well as some special cases (see, for example, Reference 9Reference 12Reference 13). Such bounds are especially powerful since such a bound for a given link type gives an algorithm to detect that link type, and the existence of a polynomial bound ensures that the detection is in NP. For an arbitrary link diagram a bound exponential in the number of crossings of , has been proven to exist by Reference 3, so there exists an algorithm that can determine whether two diagrams are related by Reidemeister moves (and therefore whether the links are equivalent). In section 6 we provide the first lower bound on the complexity of this problem by proving that the decision problem of determining whether two diagrams are related by at most Reidemeister moves is NP–hard.

Every section that follows is devoted to one of the above problems. While the most interesting results are perhaps the ones that concern Reidemeister moves and unlinking number, we put the sections in the order that makes it easier for the reader to follow the proofs, since some of the arguments can be seen as refinements of the others.

## 2. The unlink as a sublink problem

The sublink problem asks “Given diagrams of two links, is there a sublink of the first that is isotopic to the second?” Lackenby showed that this problem is NP–hard using a Karp reduction (see Section 3.1.2 in Reference 7) from the hamiltonian path problem Reference 14. Here we examine the unlink as a sublink problem, in which the second link is an unlink.

unlink as a sublink: Given a diagram for a link and a positive integer is there a , sublink of -component that is an unlink?

Note that NP–hardness of the sublink problem as proven in Reference 14 follows immediately as a corollary, since every instance of unlink as a sublink is also an instance of the sublink problem.

## 3. Unlinking number

We next consider the problem of calculating the unlinking number of a link. The *unlinking number* of a link is the minimum number of crossing changes required to become an unlink, minimized over all diagrams of the link. The definition can also be formulated without reference to knot diagrams as is described below.

An arc alone does not uniquely determine a given unlinking move, as the link in Figure 4 (b) might twist around the arc. Rather, there are infinitely many different unlinking moves that can be performed for any given arc. However, for our purposes distinguishing these moves is not important; we only need a way to represent where an unlinking move occurs.

A finite collection of unlinking moves can be represented by a collection of disjoint arcs with disjoint regular neighborhoods. Then each unlinking move does not affect the neighborhoods of the arcs associated with the other unlinking moves. Therefore, all unlinking moves in such a collection can be performed simultaneously or in any order without changing the resulting link.

With this definition, the unlinking number of a link can be defined as the smallest number of unlinking moves needed to change the link into the unlink. Since unlinking moves are defined by paths in the link complement, they are independent of the link diagram. Hence one can take the smallest number of unlinking moves for one given link diagram, unlike with crossing changes, where the number of changes is minimized across all link diagrams.

Nonetheless, the two definitions of unlinking number are equivalent. Any crossing change is an unlinking move corresponding to the vertical arc connecting the two points of the crossing. For the other direction, given a collection of unlinking moves, first perform an isotopy of to make all of the unlinking move arcs perpendicular to a plane This can be done by first choosing a thin regular neighborhood of each arc, performing an isotopy that shrinks the arcs until they lie in small disjoint Euclidean balls, followed by an ambient isotopy that is the identity outside the set of balls to straighten the arcs. These isotopies will also move the link . Once all arcs are straight and perpendicular to . project , to After applying a small perturbation of . away from the arcs if necessary, the result of this projection will be a link diagram by general position arguments. Then each unlinking move’s arc is a crossing arc in the diagram. However, it is not yet true that the unlinking moves correspond to the obvious crossing changes. If the unlinking move twists about its arc, we must additionally perform an isotopy to remove this twisting. Such an isotopy will introduce new crossings, and by slightly perturbing the diagram we can ensure again that all crossings are distinct. At the end of this process, each unlinking move corresponds to a crossing change in the diagram as desired.

Thus, given a diagram of and a set of crossing changes turning into the unlink, there is a set of unlinking moves making into an unlink. Conversely, if there is a set of unlinking moves making into an unlink then there is a diagram for which crossing changes make an unlink. Therefore, the minimum number of crossing changes needed to make an unlink is the same as the minimum number of unlinking moves needed.

unlinking number: Given a link diagram and an integer does the link have unlinking number , ?

It is not known whether unlinking number is computable, and it is not expected to be in NP Reference 11. Below, we prove that it is NP–hard (Theorem 3). The difficulty with finding a polynomial certificate lies in the fact that crossing changes required to efficiently get an unlink may not be visible in a given diagram. However one can consider the following restricted problem.

diagrammatic unlinking number: Given a link diagram and an integer can the link be made into an unlink by , crossing changes in the diagram ?

The restricted problem is NP–complete, which we will prove as a corollary to the proof of Theorem 3.

We will prove this by modifying our construction for the unlink as a sublink problem. In we replace each variable component with its untwisted Whitehead double. Figure ,5 demonstrates the replacement for a single Hopf link. We continue to refer to the Whitehead doubled variable components as variable components.

In the resulting link, any variable component can be made into an unknot unlinked from the remainder of the diagram using a single crossing change. In fact, there are two such distinct crossing changes, but they determine only one unlinking move. This is the same unlinking move that is determined by any crossing change in a standard diagram of a Whitehead link. We call this unlinking move an *unclasping move*. Using such unlinking moves followed by Reidemeister moves we can replace variable components from the connected diagram that we have with an unlink, disjoint from the rest of the diagram. Moreover, if there exists a set of -component unlinking moves resulting in the unlink, then Lemma 4(a) asserts that there exists another set of unlinking moves, also resulting in the unlink, such that any move involving a variable component is an unclasping move for that component. The second part of the lemma (Lemma 4(b)) will be used in Section 4.

Here and further, if is a link and is a component of denote by , the sublink of consisting of components other than .

We can now prove Theorem 3.

While we do not use this directly, we note that Theorem 1.2 from Reference 2 shows that there is a unique way, up to a certain natural notion of equivalence, to unknot by a crossing change a Whitehead double of any knot but the figure-eight.

## 4. Splitting and unknotting numbers

There are two other natural problems related to unlinking number. The first is the unknotting number problem, which is the restriction of the unlinking number problem to single component links.

unknotting number: Given a knot diagram and an integer does the knot shown have unknotting number , ?

The next is the problem of calculating the splitting number of a link.

As with the unlinking number, the splitting number can also be formulated without reference to diagrams by using unlinking moves. Specifically, it is the minimum number of unlinking moves needed to change a link into a split link. Variations of the splitting number have also been analyzed in the literature (see, for example, Reference 11 for details). For example, while the splitting number only requires one separating 2-sphere in the link complement, the *total splitting number* asks for the minimum number of crossing changes needed to ensure that every component is split by a 2-sphere from the other components.

splitting number: Given a link diagram and an integer does the link have splitting number , ?

The unknotting number and splitting number problems can also be rephrased as upper bound problems with “number at most Although rephrasing in this way changes the problems, it does not affect the property of being NP–hard. Indeed, ”. calls to an oracle solving the exact value problem is sufficient to solve the upper bound problem, while two calls to an oracle for the upper bound problem will solve the exact value problem. Since both the crossing number and splitting number are bounded by the crossing number and therefore the size of the input, both reductions are polynomial.

If one tries to extend the proof of Theorem 3 to the unknotting number, the main difficulty is that an unknotting number is known only for few specific classes of knots. Therefore, when constructing a new knot corresponding to a given 3–SAT instance, it is hard to show that there are no unexpected ways of unknotting it. Nonetheless, we conjecture:

We will use methods similar to the ones in Theorem 3 to prove the following theorem.

We start with two preliminary lemmas.

We now begin the construction.

## 5. Alternating sublinks

We next consider another variation of the sublink problem.

alternating sublink: Given a diagram of a link and a positive integer does , have a sublink that is alternating? -component

Note that unlike the sublink problem as proposed by Lackenby and the special case unlink as a sublink analyzed in Theorem 1, the problem above asks not for a specific sublink, but a sublink with a given property.

We need the following lemma: