12
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 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$ – Arnaud Nov 6 '14 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$ – Arnaud Nov 6 '14 at 12:38
  • $\begingroup$ thanks for your precision: I've included it into the text. $\endgroup$ – Noam Zeilberger Nov 6 '14 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$ – Abel Molina Nov 11 '14 at 19:57
  • 1
    $\begingroup$ no, you're right, I was just being dense. Fixed now. $\endgroup$ – Noam Zeilberger Nov 12 '14 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.