Timeline for Why is it so hard to implement Haken's Algorithm for knot theory?
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2011 at 17:02 | vote | accept | Hu Yi Chen | ||
| Jan 27, 2011 at 17:43 | history | edited | Sam Nead | CC BY-SA 2.5 |
fixed grammar, formatting
|
| Jan 26, 2011 at 23:46 | answer | added | Ben Burton | timeline score: 30 | |
| Jan 25, 2011 at 20:24 | comment | added | Joseph O'Rourke | Thanks, Peter (but no one can edit comments--Alas!). Here is the arXiv pre-publication version, which might be more accessible: arxiv.org/abs/math/9807016 . | |
| Jan 25, 2011 at 20:18 | comment | added | Peter Shor | @Jim: It looks like Joe already edited his comment to answer your question, but here's a link to the Hass, Lagarias and Pippenger article: portal.acm.org/citation.cfm?id=301970.301971 | |
| Jan 25, 2011 at 20:05 | comment | added | Jim Conant | @Joseph O'Rourke: do you know of a reference for the fact that unknotting is an NP problem? | |
| Jan 25, 2011 at 20:01 | comment | added | Joseph O'Rourke | Re complexity: This doesn't answer your question definitively (maybe others will), but: (a) Unknotting is in NP, and (b) there is an upper bound exponential in the number of crossings. Haas, Lagarias, and Pippenger are responsible for these results. | |
| Jan 25, 2011 at 19:23 | answer | added | Bill Thurston | timeline score: 21 | |
| Jan 25, 2011 at 19:21 | comment | added | gowers | I'd like to add the following question: what is the best known efficiency of such an algorithm (in terms of the number of crossings of the knot diagram, say)? | |
| Jan 25, 2011 at 19:11 | answer | added | Ryan Budney | timeline score: 18 | |
| Jan 25, 2011 at 19:00 | history | asked | Hu Yi Chen | CC BY-SA 2.5 |