From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: Re: A Bound for the Unknot Problem Date: 10 Feb 2001 13:17:26 -0800 Newsgroups: sci.math.research Summary: How hard can it be to recognize and untangle the unknot? In article <20010209010555.00322.00000128@ng-bd1.aol.com>, MikeAt1140 wrote: >"Lagarias and Hass guarantee is that if a knot crosses itself n times, you can >untangle it in no more than 2^100,000,000,000n Reidemeister moves." > >The previous discussion in the article assumes the knot in question is >equivalent to the unknot. > >Has this result been verified? Joel Hass happens to be here at UC Davis, except that he is on sabbatical this year. A year or two ago I devoted some attention to the Hass-Lagarias argument. The argument is based on Haken's algorithm from the 1960's for determining whether or not a knot is the unknot. It has taken a long time to understand the implications of Haken's algorithms in 3-manifold topology. The Hass-Lagarias paper is in the arXiv [math.GT/9807012]. I haven't verified the *paper* page by page. But I am absolutely convinced that their *argument* works and gives you a C^n bound on Reidemeister moves. I haven't verified any specific value of C either, but if you wanted a good upper bound, people expect polynomial rather than exponential. One piece of evidence in favor of a polynomial bound is Bill Thurston's result that if a braid word is trivial, you can untangle it using a quadratic number of moves. And at least in this case, you can find the moves quickly too! This is explained in the book "Word Processing in Groups". Bill is at UC Davis too and he has conjectured to me that the same phenomena, namely a polynomial number of moves that can be found in polynomial time, also hold for the unknot. No one has ever found a mysterious presentation of the unknot. By contrast in 4-dimensional topology there are all kinds of mysterious manifolds that may or may not be PL homeomorphic to S^4, even despite the massive hint that they're *continuously* homeomorphic to S^4. -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/ \/ * All the math that's fit to e-print * ============================================================================== From: lrudolph@panix.com (Lee Rudolph) Subject: Re: A Bound for the Unknot Problem Date: 10 Feb 2001 18:06:54 -0500 Newsgroups: sci.math.research greg@math.ucdavis.edu (Greg Kuperberg) writes: ... >result that if a braid word is trivial, you can untangle it using a >quadratic number of moves. And at least in this case, you can find the >moves quickly too! This is explained in the book "Word Processing in >Groups". Bill is at UC Davis too and he has conjectured to me that the >same phenomena, namely a polynomial number of moves that can be found >in polynomial time, also hold for the unknot. No one has ever found >a mysterious presentation of the unknot. Well, that is somewhat dependent on what you mean by "mysterious". As R. C. Gunning pointed out when asked if a something was "deep mathematics", mathematics rises to the surface with time; and mysteries become less mysterious. Way back in 1982 I found a 4-string braid presenting the 2-component unlink (shortly thereafter improved by Hugh Morton to a 4-string braid representing the unknot) in what seemed to me at the time an adequately mysterious way. (The braids we found are *very* distinct from the obvious 4-braids with the same closures, in a way that can be described in purely algebraic language, or equivalently--and more perspicuously-- in geometrical language by saying that the closed braids don't bound braided disks.) Last year Gretchen Wright took away probably the last bit of mystery from those particular examples (using recent techniques of Joan Birman _et al._), but there might still be some mysterious presentations of the unknot around, for appropriate values of "mysterious". Lee Rudolph ============================================================================== From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: Re: A Bound for the Unknot Problem Date: 11 Feb 2001 10:03:58 -0800 Newsgroups: sci.math.research In article <964hie$3eb$1@panix5.panix.com>, Lee Rudolph wrote: >>No one has ever found a mysterious presentation of the unknot. >Well, that is somewhat dependent on what you mean by "mysterious". I didn't have any rigorous meaning in mind, but the idea is to construct complications in the presentation that go in the direction of being NP-hard. (Interestingly, by another result of Hass, Lagarias, and Pippenger, unknottedness is in NP, so NP-hardness would imply NP-completeness.) Thurston's point is that even when you haven't proven that a problem is NP-hard, it might at least give you the strong feeling of being so. For example, there are the popular puzzles with strings, rigid pieces, and hinges, where typically the challenge is to remove a ring. These are so annoying that the natural conjecture is that they are at least NP-hard. Some of them take an exponential number of moves and these could in principle be even harder. Certainly presentations of S^4 have the same reputation, even though it is only a conjecture that standardizing such a presentation is hard. Admittedly there are other 4-manifolds for which standardization is known to be non-recursive, never mind NP-hard. -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/ \/ * All the math that's fit to e-print *