<p>You can take a look to:</p>

<p>Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. <a href="http://dl.acm.org/citation.cfm?id=1566503&amp;dl=ACM&amp;coll=DL&amp;CFID=595548980&amp;CFTOKEN=43280830">Tricolorable torus knots are NP-complete</a>. In Proceedings of the 47th Annual Southeast Regional Conference (ACM-SE 47). ACM, New York, NY, USA, , Article 42 , 6 pages. </p>

<p><strong>Abstract:</strong> This work presents a method for associating a class of constraint satisfaction problems to a three-dimensional knot. Given a knot, one can build a knot quandle, which is generally an infinite free algebra. The desired collection of problems is derived from the set of invariant relations over the knot quandle, applying theory that relates finite algebras to constraint satisfaction problems. This allows us to develop notions of tractable and NP-complete quandles and knots. In particular, we show that all tricolorable torus knots and all but at most 2 non-trivial knots with 10 or fewer crossings are NP-complete.</p>

<p>and also to its seminal report: </p>

<p>P. Golbus, R. W. McGrail, M. Merling, K. Ober, M. Sharac, and J. Wood. <a href="http://www.math.jhu.edu/~mmerling/docs/knots.pdf">The class of constraint satisfaction problems over a knot</a>. Technical Report number
BARD-CMSC-2008-01, Bard College, 2008.</p>

CC BY-SA 3.0
2014-11-06T14:44:02.443Z
2014-11-06T14:44:02.443Z
Marzio De Biasi
<p>There are a few references in the first paragraph of</p>

<ul>
<li>Marc Lackenby. A polynomial upper bound on Reidemeister moves. <a href="http://arxiv.org/abs/1302.0180" rel="nofollow" title="arXiv:1302.0180">arXiv:1302.0180</a></li>
</ul>

<p>In particular, the author says that the problem of recognizing that a knot diagram represents the unknot is in $\mathbf{NP} \cap \mathbf{coNP}$, by combining a result of Hass-Lagarias-Pippenger (that unknottedness is in NP) with independent results of Agol and Kuperberg (that knottedness is in NP, the latter proving this under assumption of the generalized Riemann hypothesis).  The Agol result seems to be unpublished, but the other references are:</p>

<ul>
<li><p>Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The Computational Complexity of Knot and Link Problems. J. ACM 46 (1999) 185-211. <a href="http://arxiv.org/abs/math/9807016" rel="nofollow">arXiv:math/9807016</a></p></li>
<li><p>Greg Kuperberg. Knottedness is in NP, modulo GRH. December 2011, revised January 2014. <a href="http://arxiv.org/abs/1112.0845" rel="nofollow">arXiv:1112.0845</a></p></li>
</ul>

<p>I also found another related paper by Agol, Hass, and Bill Thurston, where they show that the more general problem of determining whether a knot [in an arbitrary closed 3-manifold] has genus at most $g$ is NP-complete:</p>

<ul>
<li>Ian Agol, Joel Hass, William Thurston. 3-MANIFOLD KNOT GENUS is NP-complete. STOC 2002. <a href="http://dl.acm.org/citation.cfm?id=510016" rel="nofollow">ACM link</a></li>
</ul>

<p>I am interested in other examples as well. </p>

CC BY-SA 3.0
2014-11-06T12:34:23.880Z
The never published co-NP proof of Agol using sutured hierarchies is briefly summarized in a recent survey of Lackenby: http://people.maths.ox.ac.uk/lackenby/ekt11214.pdf
Arnaud
CC BY-SA 3.0
2014-11-06T12:38:31.863Z
And a small precision: the Agol, Hass, Thurston NP-hardness proof only applies in general 3-manifolds, and not for knot genus in $\mathbb{R}^3$. Very few hardness results are known for topological problems in $\mathbb{R}^3$ and $\mathbb{S}^3$.
Arnaud
CC BY-SA 3.0
2014-11-06T12:45:46.110Z
thanks for your precision: I've included it into the text.
Noam Zeilberger
CC BY-SA 3.0
2014-11-11T19:57:16.320Z
Maybe being dense here, but not clear why the results are characterized in the answer as talking about knottedness/unknottedness "being NP-hard", rather than "being in NP", since as far as I can see in the abstract, they assert that the problems are in NP, but not that they are NP-Complete as well.
Abel Molina
CC BY-SA 3.0
2014-11-12T08:04:37.817Z
no, you're right, I was just being dense. Fixed now.
Noam Zeilberger
CC BY-SA 3.0
2014-11-06T12:26:13.083Z
2014-11-12T08:04:11.233Z
2014-11-12T08:04:11.233Z
Noam Zeilberger
<p>A fairly recent knot theoretic related result to do with NP hardness, or NP completeness are the following <a href="https://dl.acm.org/doi/10.5555/3458064.3458154" rel="nofollow noreferrer">results</a> that show finding that a link has a splitting number <em><strong>k</strong></em> is NP-hard. Other link problems that are shown to be  NP-hard, are those of finding a <em><strong>k</strong></em>-component unlink as a sublink, and <em><strong>k</strong></em>-component alternating sublink.</p>
<p>Lackenby showed UNLINK as a SUBLINK is NP-complete. For more about <a href="https://link.springer.com/article/10.1007/s00454-017-9905-8" rel="nofollow noreferrer">Lackenby's</a> proof about UNLINK, and related linking to the SUBLINK problem. The proof of the SUBLINK problems in the first paper are approached by the NP-hardness of UNLINK by way of Reidemeister moves.</p>

CC BY-SA 4.0
2024-03-30T01:38:41.163Z
2024-03-30T12:52:42.260Z
2024-03-30T12:52:42.260Z
user3483902
<p>Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones polynomial. Graph problems(embeddings?), specifically colourings of graphs can be seen to have nice knot theoretic properties. It is an open ended question, and any references for this topic appreciated. </p>

<ct.category-theory><np>
Are there knot theoretic formulations of NP complete problems?
user3483902
# Are there knot theoretic formulations of NP complete problems?

(Asked by: username_0 on 2014-11-05)

Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones polynomial. Graph problems(embeddings?), specifically colourings of graphs can be seen to have nice knot theoretic properties. It is an open ended question, and any references for this topic appreciated.

**Tags:** ct.category-theory, np


---

## 3 answers

### Answer by username_1 on 2014-11-06. Score: 12

You can take a look to:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, and Aleksandar Chakarov. 2009. [Tricolorable torus knots are NP-complete](http://dl.acm.org/citation.cfm?id=1566503&dl=ACM&coll=DL&CFID=595548980&CFTOKEN=43280830). In Proceedings of the 47th Annual Southeast Regional Conference (ACM-SE 47). ACM, New York, NY, USA, , Article 42 , 6 pages.

**Abstract:** This work presents a method for associating a class of constraint satisfaction problems to a three-dimensional knot. Given a knot, one can build a knot quandle, which is generally an infinite free algebra. The desired collection of problems is derived from the set of invariant relations over the knot quandle, applying theory that relates finite algebras to constraint satisfaction problems. This allows us to develop notions of tractable and NP-complete quandles and knots. In particular, we show that all tricolorable torus knots and all but at most 2 non-trivial knots with 10 or fewer crossings are NP-complete.

and also to its seminal report:

P. Golbus, R. W. McGrail, M. Merling, K. Ober, M. Sharac, and J. Wood. [The class of constraint satisfaction problems over a knot](http://www.math.jhu.edu/~mmerling/docs/knots.pdf). Technical Report number
BARD-CMSC-2008-01, Bard College, 2008.


---

### Answer by username_2 on 2014-11-06. Score: 10

There are a few references in the first paragraph of

* Marc Lackenby. A polynomial upper bound on Reidemeister moves. [arXiv:1302.0180](http://arxiv.org/abs/1302.0180 "arXiv:1302.0180")

In particular, the author says that the problem of recognizing that a knot diagram represents the unknot is in $\mathbf{NP} \cap \mathbf{coNP}$, by combining a result of Hass-Lagarias-Pippenger (that unknottedness is in NP) with independent results of Agol and Kuperberg (that knottedness is in NP, the latter proving this under assumption of the generalized Riemann hypothesis). The Agol result seems to be unpublished, but the other references are:

* Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The Computational Complexity of Knot and Link Problems. J. ACM 46 (1999) 185-211. [arXiv:math/9807016](http://arxiv.org/abs/math/9807016)
* Greg Kuperberg. Knottedness is in NP, modulo GRH. December 2011, revised January 2014. [arXiv:1112.0845](http://arxiv.org/abs/1112.0845)

I also found another related paper by Agol, Hass, and Bill Thurston, where they show that the more general problem of determining whether a knot [in an arbitrary closed 3-manifold] has genus at most $g$ is NP-complete:

* Ian Agol, Joel Hass, William Thurston. 3-MANIFOLD KNOT GENUS is NP-complete. STOC 2002. [ACM link](http://dl.acm.org/citation.cfm?id=510016)

I am interested in other examples as well.

> **Comments:**
> **username_3**: The never published co-NP proof of Agol using sutured hierarchies is briefly summarized in a recent survey of Lackenby: http://people.maths.ox.ac.uk/lackenby/ekt11214.pdf  
> **username_3**: And a small precision: the Agol, Hass, Thurston NP-hardness proof only applies in general 3-manifolds, and not for knot genus in $\mathbb{R}^3$. Very few hardness results are known for topological problems in $\mathbb{R}^3$ and $\mathbb{S}^3$.  
> **username_2**: thanks for your precision: I've included it into the text.  
> **username_4**: Maybe being dense here, but not clear why the results are characterized in the answer as talking about knottedness/unknottedness "being NP-hard", rather than "being in NP", since as far as I can see in the abstract, they assert that the problems are in NP, but not that they are NP-Complete as well.  
> **username_2**: no, you're right, I was just being dense. Fixed now.  

---

### Answer by username_0 on 2024-03-30. Score: 2

A fairly recent knot theoretic related result to do with NP hardness, or NP completeness are the following [results](https://dl.acm.org/doi/10.5555/3458064.3458154) that show finding that a link has a splitting number ***k*** is NP-hard. Other link problems that are shown to be NP-hard, are those of finding a ***k***-component unlink as a sublink, and ***k***-component alternating sublink.

Lackenby showed UNLINK as a SUBLINK is NP-complete. For more about [Lackenby's](https://link.springer.com/article/10.1007/s00454-017-9905-8) proof about UNLINK, and related linking to the SUBLINK problem. The proof of the SUBLINK problems in the first paper are approached by the NP-hardness of UNLINK by way of Reidemeister moves.


---

