7
$\begingroup$

In knot theory, two link diagrams are equivalent if and only if they can be related by performing a finite number of Reidemeister moves. But sometimes it is so confusing that I don't know which type move should I perform on link to get desired result. Is there an efficient procedure to relate one link diagram to another provided we know that the two links are equivalent? What is the computational complexity of determining knot equivalence? Is it NP complete?

Also, a related question: Is there any computer software which efficiently finds Reidemeister moves between equivalent diagrams? Because sometimes I find it is very difficult to visualise the link after some Reidemeister moves.

Improve this question
$\endgroup$
7
  • $\begingroup$ Perhaps we could focus your question by asking for a feasible procedure, rather than merely a computational procedure (since otherwise one could simply undertake an exhaustive search). So a related question might be: what is the computational complexity of determining knot equivalence? Is it NP complete? How complex is it to find the witnessing sequence of moves? $\endgroup$
    – Joel David Hamkins
    Commented Nov 6, 2013 at 15:19
  • 1
    $\begingroup$ See gilkalai.wordpress.com/2012/04/10/…, which explains that Greg Kuperberg has proved under GRH that the special case of determining if a knot is trivial is in NP. This by itself doesn't seem to answer the question of finding the moves when it is known that two knots are equivalent, but it is clearly related. Greg's paper: front.math.ucdavis.edu/1112.0845 $\endgroup$
    – Joel David Hamkins
    Commented Nov 6, 2013 at 15:26
  • 2
    $\begingroup$ You might like to look at this old question of Gowers on whether there are trivial knots that are tricky to "undo". mathoverflow.net/questions/53471/… $\endgroup$
    – Ben Barber
    Commented Nov 6, 2013 at 15:29
  • $\begingroup$ And in the context of Borel equivalence relations, it seems that knot equivalence is very high in the hierarchy under Borel reducibility. See logic.univie.ac.at/2012/Talk_10-04_a.html $\endgroup$
    – Joel David Hamkins
    Commented Nov 6, 2013 at 15:30
  • $\begingroup$ For trivial, hyperbolic and torus links there's certain anecdotal evidence that supports the idea there is a flow to a more-or-less canonical position (up to conformal diffeo). But this would be in terms of a physical knot rather than diagram crossing changes. But for more complicated links there does not appear to be natural ways to relate the position of one to the position of another. You might want to try using software like "knotscape" to play around with these flows. $\endgroup$
    – Ryan Budney
    Commented Nov 6, 2013 at 16:14

2 Answers 2

Reset to default
7
$\begingroup$

In 2011 Coward-Lackenby proved the following, and they also provided an upper bound on the number of moves.

There is a computable function F : N×N → N such that for any two connected diagrams D1 and D2 of a link with n1 and n2 crossings, there is a sequence of at most F(n1, n2) Reidemeister moves that takes D1 to D2.

There is an algorithm to solve the equivalence problem for links. In other words, there is an algorithm that takes as input two link diagrams and determines whether or not they represent equivalent links.

The paper may contain arguments and references relevant to your question http://people.maths.ox.ac.uk/lackenby/rei17611.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ This asserts finding moves between one knot diagram and another isn't a hopeless cause, but it's not efficient. I don't know where people draw the line on the word "efficient" but I usually want it to mean sub-exponential growth, or minimally "not very bad" exponential growth. $\endgroup$
    – Ryan Budney
    Commented Nov 6, 2013 at 17:31
5
$\begingroup$

I think yanglee's answer gives the state-of-the-art as far as determining how many Reidemeister moves are needed to get between diagrams of equivalent knots.

It is not known that knot recognition is NP-complete.

For software to find equivalent diagrams, I would try out the program Gridlink written by Marc Culler, which allows one to experiment with grid diagrams of links, and perform the corresponding grid moves. If two projects of knots in grid position are equivalent by Reidemeister moves, then they will be equivalent by the grid moves. I think grid diagrams are easier to work with computationally and to render output on a computer. The Kirby calculator also allows certain Reidemeister moves to be performed, but is not specifically designed for this purpose.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .