tag:blogger.com,1999:blog-6555947.post108813635839424593..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: Knot or not ? Suresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6555947.post-1088220389662493562004-06-25T21:26:00.000-06:002004-06-25T21:26:00.000-06:00Yes, so the claim "too complex to apply even in si...Yes, so the claim "too complex to apply even in simple cases" is rather misleading. It actually gives the impression that NO general algorithm exists.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1088191952010829302004-06-25T13:32:00.000-06:002004-06-25T13:32:00.000-06:00In particular, Hass, Lagarias, and Pippenger reduc...In particular, Hass, Lagarias, and Pippenger reduce the unknonttedness question to an integer programming problem, which can be solved in sinlgy-exponential time, via a technique of Haken called "normal surface theory". This improves the quadruply-exponential running time of Haken's 1961 algorithm.<br /><br />(I'm astounded at MathWorld's assertion that "there is no general algorithm" to detect unknotedness, especially since the assertion is immediately followed by a reference to a general algorithm! Yeah, Haken's algorithm is slow. So what?!)Jeff Ericksonhttp://www.blogger.com/profile/08256919779078679044noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1088177146664502802004-06-25T09:25:00.000-06:002004-06-25T09:25:00.000-06:00The following paper by Hass, Lagarias and Pippenge...The following paper by Hass, Lagarias and Pippenger<br />addresses the complexity of knot problems. They show<br />that some of the problems are in NP and some in PSPACE.<br /><br />article{301971,<br /> author = {Joel Hass and Jeffrey C. Lagarias and Nicholas Pippenger},<br /> title = {The computational complexity of knot and link problems},<br /> journal = {J. ACM},<br /> volume = {46},<br /> number = {2},<br /> year = {1999},<br /> issn = {0004-5411},<br /> pages = {185--211},<br /> doi = {http://doi.acm.org/10.1145/301970.301971},<br /> publisher = {ACM Press},<br /> }<br /><br />ChandraAnonymousnoreply@blogger.com