Subject: Re: Unknotting algorithm [for toplist]
Date: Mon, 19 Feb 2001 10:05:32 -0800
From: Greg Kuperberg <greg@math.ucdavis.edu>

Brian Sanderson:
> How long does it take to see if a knot diagram with n crossings represents
> the unknot? I believe a bound on the number of steps needed to perform
> Haken's algorithm  has been found recently.

Haken's algorithm produces a disk (or one of several disks) whose boundary
is the given unknot.  In arXiv:math.GT/9807012, Hass and Lagarias give
an exponential upper bound for the combinatorial area of a Haken disk.
The argument for this bound is exactly the same as the argument that
Haken's algorithm terminates in the first place.  Regardless of how
long it takes to find the disk ("steps needed to perform the algorithm"
in your terminology), this gives you an exponential upper bound on the
number of Reidemeister moves you need to remove all of the crossings.
The bound on moves is probably lousy; the natural conjecture is a
polynomial number of moves.  But as Hass, Snoeyink, and Thurston show
in arXiv:math.GT/9906917, it is a reasonable bound on the area of a
spanning disk, because you can force that to grow exponentially in the
number of crossings.

In many expositions people stop at suggesting an exhaustive search
for finding a Haken disk, which would take double exponential time, or
C^(C^n).  But another article by Hass and Lagarias, arXiv:math.GT/9807016,
shows that existence of the disk is an NP problem, which means that
the disk can be found in time C^(n^k) for some k; I think it's actually
C^(n^2).  The point is that although the disk may be large,
it admits a polynomial encoding because it has many repeated folds.
--
  /\  Greg Kuperberg (UC Davis)
 /  \
 \  / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/
  \/  * All the math that's fit to e-print *