A recent posting on comp.theory prompted this note:
given the 3 dimensional layout of a rope, I would like to know if
pulling the strings at both ends would result is knot or not.
MathWorld had this to say:
There is no general algorithm to determine if a tangled curve is a knot or if two given knots are interlocked. Haken (1961) and Hemion (1979) have given algorithms for rigorously determining if two knots are equivalent, but they are too complex to apply even in simple cases (Hoste et al. 1998).
Note that the question MathWorld asks appears to be slightly more general (asking if a given curve is a knot or not). The question by the comp.theory poster (I imagine) only asks about a motion pulling in two opposite directions (although this is probably not the most precise way to put it).
I imagine that the answer to the question posted above is well known: I'd be interested in a pointer if anyone has one.
There are a plethora of links on the web concerning knot theory. The Geometry Junkyard has a knot theory page, and a far more comprehensive set of links can be found at Knots On The Web.
The following paper by Hass, Lagarias and Pippenger
ReplyDeleteaddresses the complexity of knot problems. They show
that some of the problems are in NP and some in PSPACE.
article{301971,
author = {Joel Hass and Jeffrey C. Lagarias and Nicholas Pippenger},
title = {The computational complexity of knot and link problems},
journal = {J. ACM},
volume = {46},
number = {2},
year = {1999},
issn = {0004-5411},
pages = {185--211},
doi = {http://doi.acm.org/10.1145/301970.301971},
publisher = {ACM Press},
}
Chandra
Yes, so the claim "too complex to apply even in simple cases" is rather misleading. It actually gives the impression that NO general algorithm exists.
ReplyDelete