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.
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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. 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. Technical Report number BARD-CMSC-2008-01, Bard College, 2008.
answered Nov 6, 2014 at 14:44
$\begingroup$
$\endgroup$
5
There are a few references in the first paragraph of
- Marc Lackenby. A polynomial upper bound on Reidemeister moves. 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
Greg Kuperberg. Knottedness is in NP, modulo GRH. December 2011, revised January 2014. arXiv: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
I am interested in other examples as well.
-
3$\begingroup$ The never published co-NP proof of Agol using sutured hierarchies is briefly summarized in a recent survey of Lackenby: people.maths.ox.ac.uk/lackenby/ekt11214.pdf $\endgroup$– ArnaudCommented Nov 6, 2014 at 12:34
-
3$\begingroup$ 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$. $\endgroup$– ArnaudCommented Nov 6, 2014 at 12:38
-
$\begingroup$ thanks for your precision: I've included it into the text. $\endgroup$ Commented Nov 6, 2014 at 12:45
-
2$\begingroup$ 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. $\endgroup$ Commented Nov 11, 2014 at 19:57
-
1$\begingroup$ no, you're right, I was just being dense. Fixed now. $\endgroup$ Commented Nov 12, 2014 at 8:04
$\begingroup$
$\endgroup$
A fairly recent knot theoretic related result to do with NP hardness, or NP completeness are the following results 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 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.
