Given a composite knot, is it possible to decompose it in prime knots by an algorithm that runs in polynomial time?

  • 1
    $\begingroup$ What is your motivation for this? And what is your understanding of the situation up until now? $\endgroup$
    – David Roberts
    Commented Dec 13, 2011 at 23:56
  • $\begingroup$ My understanding of present knowledge is that the answer is it's not known, but highly doubtful that such an algorithm exists. $\endgroup$ Commented Dec 14, 2011 at 0:40
  • 1
    $\begingroup$ I think current run-time estimates for known algorithms to construct the prime decomposition of a knot tend to be at least exponential. I'm thinking of normal surface theory arguments. $\endgroup$ Commented Dec 14, 2011 at 0:41
  • 7
    $\begingroup$ A straightforward comment is that this problem is at least as hard as recognizing the unknot. (Given a diagram D for knot, form a larger diagram as the "connected sum" of D with a trefoil diagram. The larger diagram represents a composite knot iff D represents the unknot.) $\endgroup$ Commented Dec 14, 2011 at 13:45
  • $\begingroup$ I know that in computational topology, there are several softwares like SnapPea and Regina, designed to help topologists in the resolutions of hard problems. I am studying knot theory in this period and then i would like to know if it is possbile (thanks to these programs or other softwares) to decompose a (non prime) knot by an algorithm that runs in polynomial time! $\endgroup$
    – Gian
    Commented Dec 14, 2011 at 17:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.