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/