Recognition and Generation of Knots and Links
2.1 Recognition of KLs
According to D.J.A.Welsh (1993), two fundamental algebraic problems about KLs are:
Those two problems are almost inseparable and go together with the question about a crossing number of a KL, this means, an algorithm for its minimization. In the case of rational KLs all those problems were solved in a very simple, elegant and fast way (in the sense of algorithms), thanks to the connection between rational KLs and continued fractions. When stepping outside the rational world do these problems arise. For the unknotting problem (and the unknotting number problem) we propose a finite algorithm based on Bernhard-Jablan Conjecture. The starting point of this algorithm is a minimal projection of a certain KL. Next steps are: making crossing change in each vertex of the projection and then minimizing obtained results. This process is continued until the KL is unknotted (unlinked). However, that algorithm is based on the Knot 2000 (K2K) function ReductionKnotLink that sometimes fails in a minimization. This holds even for much better heuristic program for reduction of knots knotfind.c written by M. Thistlethwaite and used as a part of the program Knotscape. Its first known unsuccessful reduction is for a 40-crossing knot. We implemented a computer algorithm for recognizing alternating KLs given in Conway notation using the fact that two alternating KLs are equal iff their minimal Dowker codes are equal. Therefore, LinKnot function SameAltConKL (webMathematica SameAltConKL) for two given alternating KLs computes their minimal Dowker codes and compares them. In case they are equal, the result is 1, otherwise 0.