tag:blogger.com,1999:blog-6555947.post110686173740745120..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Unknotting...Suresh Venkatasubramaniannoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-1107607565582284652005-02-05T05:46:00.000-07:002005-02-05T05:46:00.000-07:00Suresh, I don't think I've yet knitted a knot; I h...Suresh, I don't think I've yet knitted a knot; I have baked knotted bagels (trefoil) and knotted challa (figure-8). However, a measure 1 subset of the knot theory done in my household is done by someone else. <br /><br /><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.blogger.com/r?http%3A%2F%2Flearningcurves.blogspot.com" TITLE="srudbeckiahirta at yahoo dot com">Rudbeckia Hirta</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1107561765625862092005-02-04T17:02:00.000-07:002005-02-04T17:02:00.000-07:00This comment has been removed by a blog administrator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1107552483252797812005-02-04T14:28:00.000-07:002005-02-04T14:28:00.000-07:00Well said, Jeff. I actually have a post lined up t...Well said, Jeff. I actually have a post lined up that talks about this, liberally referencing a stunning lecture given by Timothy Gowers a few years ago on the importance of math (where he mentions knot theory, btw).<br /><br />In short, mathematicians like math for various reasons, but very few of these reasons have to do with so-called "practical impact". I would not object if some of my work has some practical relevance, but that is not necessarily my goal in pursuing it (and i'm not even a mathematician !)<br /><br />"Thunderstorms or dancing bears". There's a nice ring to that :) <br /><br /><A></A><A></A>Posted by<A><B> </B></A>SureshAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1107552104860338712005-02-04T14:21:00.000-07:002005-02-04T14:21:00.000-07:00It's (ahem) "just" because we like knots and compl...It's (ahem) "just" because we like knots and complexity. These are fundamental mathematical questions, much more important than this so-called "reality" that physicists keep arguing about. String theory is about as relevant to our interest as thunderstorms or dancing bears. <br /><br /><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.blogger.com/r?http%3A%2F%2F3dpancakes.typepad.com" TITLE="jeffe at cs dot uiuc dot edu">Jeff Erickson</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1107528783721287872005-02-04T07:53:00.000-07:002005-02-04T07:53:00.000-07:00I'm curious why you guys care about this proof. I...I'm curious why you guys care about this proof. Is it just because you like knots and complexity or is it because some allege that it's tied to string theory (see Not Even Wrong for an opinion that string theory is probably nonsense). <br /><br /><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1107526911584934692005-02-04T07:21:00.000-07:002005-02-04T07:21:00.000-07:00Translation time!
The paper relies on a construct...Translation time!<br /><br />The paper relies on a construction (due to Haken?) of a triangulated 3-dimensional manifold M(K) from a given knot K, such that M(K) is homeomorphic to the 3-sphere if and only if K is unknotted. Specifically, M(K) consists of two copies of S^3-T(K), glued along their boundaries (which are toruses), where T(K) is a tubular neighborhood of the knot K.<br /><br />So one algorithm for deciding whether a knot K is trivial is to construct M(K) and check whether M(K) is the 3-sphere. The 3-sphere recognition problem is in NP (http://front.math.ucdavis.edu/math.GT/0407047). Haas et al. used a slightly different technique to prove that UNKOTTING is in NP, but both NP-proofs rely on something called "normal surface theory" introduced by Haken in the early 1960s to boil everything down to integer programming(!).<br /><br />Hara, Tani, and Yamamoto describe an interactive proof protocol for UNKNOTTING based on this characterization, and similar to an interactive protocol for graph isomorphism. The prover is trying to convince the verifier that her knot is nontrivial. The verifier constructs two triangulated 3-manifoldsâ€”the manifold M(K) described above, and a particular triangulation S(K) of the 3-sphere. After randomly permuting the vertex labels, the verifier presents the prover with a one of the two triangulations, chosen uniformly at random, without telling the prover which it is. The prover then (supposedly) tells the verifier whether his given manifold is the 3-sphere.<br /><br />(1) If the prover says that S(K) is the 3-sphere, the verifier learns nothing.<br /><br />(2) If the prover says that S(K) is NOT the 3-sphere, the verifier knows he's lying and assumes the knot is trivial.<br /><br />(3) If the prover says that M(K) is the 3-sphere, the verifier assumes the knot is trivial.<br /><br />(4) if the prover says that M(K) is NOT the 3-sphere, the verifier assumes the knot is nontrivial.<br /><br />If the knot is trivial, then no prover can convince this verifier with probablity better than 1/2. If the knot is nontrivial, an honest prover can convince this verifier with probability 1/2. Running this protocol twice inflates the probabilities to 1/4 and 3/4.<br /> <br /><br /><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://www.blogger.com/r?http%3A%2F%2F3dpancakes.typepad.com" TITLE="jeffe at cs dot uiuc dot edu">Jeff Erickson</A>Anonymousnoreply@blogger.com