From: deej Newsgroups: sci.math.research Subject: Re: The computational complexity of knot and link problems Date: Thu, 30 Oct 1997 17:06:45 -0600 On Thu, 30 Oct 1997, Peter Shor wrote: > Hayes writes: "The algorithm was published in 1961 by Wolfgang Haken. > ... Recently, Haken's algorithm has been analyzed--and, incidentally, > explicated--by Joel Hass of the University of California at Davis, > Jeffrey C. Lagarias of AT&T Laboratories and [Nicholas] Pippenger. > The essence of the algorithm is to examine the two-dimensional surface > whose boundary is the closed path being tested for knottedness; if this > surface is topologically equivalent to a disk, then the path is the unknot. > Haken gave a procedure for determining whether or not the surface is a disk. > Hass, Lagarias and Pippenger find that the running time of a program based > on this procedure would be proportional to 2 raised to the power cr^2, > where c is a constant and r is the number of crossings in the knot diagram. > They also derived a modified algorithm with the running time 2^{cr}. Even > with this improvement, however, the algorithm is not one you would want in > the inner loop of a program." Joel Hass told me that the unknot, drawn with a single crossing, was input into said program, and after three days the computer said (correctly) that it was the unknot. However, he was only passing along what he had heard, so that this information is at least third hand... It is interesting to note that Haken's algorithm only recognizes the unknot. Put any other two knots into his algorithm, and it can only tell you that they (both) aren't unknots. It cannot tell you anything else. > Second, with respect to knots, exponential time is not necessarily infeasible > in practice, as this is also the complexity of algorithms for computing > the Jones polynomial, and I believe these work quite well for small knots. All of the knot invariants I am aware of require exponential time. Yet they are often employed; exponential time is not a serious problem when we still have huge problems open even for knots of small crossing number (such as 14). Dr. Daniel J. Heath "deej" Assistant Professor & nice guy Texas A&M - Commerce, Math deej@boisdarc.tamu-commerce.edu ============================================================================== From: eppstein@euclid.ics.uci.edu Newsgroups: sci.math.research Subject: Re: The computational complexity of knot and link problems Date: 31 Oct 97 17:51:12 GMT deej writes: > It is interesting to note that Haken's algorithm only recognizes the > unknot. Put any other two knots into his algorithm, and it can only > tell you that they (both) aren't unknots. It cannot tell you anything > else. The Hass-Lagarias-Pippenger result does more than recognizing the unknot, it can compute the genus of any knot. However, while unknot recognition is in NP, their algorithm for genus has higher complexity, maybe P^#P -- their paper in the proceedings of FOCS '97 says PSPACE but I think Pippenger said something smaller at the actual conference talk. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/