Timeline for What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2016 at 15:53 | answer | added | Dylan Thurston | timeline score: 24 | |
| Feb 28, 2016 at 6:45 | comment | added | Ryan Budney | @MikeMiller: in practice it looks like a low-degree polynomial-time complexity. This is one paper that starts to quantify these observations: arxiv.org/abs/1110.6080 | |
| Feb 28, 2016 at 6:40 | comment | added | mme | @RyanBudney: I haven't read it either; my impression is that it's heuristic, but that many examples have been computed. I was just hoping you could quantify how good normal surface theory is most of the time when you say it's usually better than exponential: is it usually polynomial? Usually $O(\exp(\sqrt n))$? Etc. | |
| Feb 28, 2016 at 6:34 | comment | added | Ryan Budney | @MikeMiller: I have not read Bar Natan's paper. How does he determine his "usually" comment, is this a general statement or one derived by computing a few examples? If you give me an answer to that I should be able to answer your question. The "usually" for the normal surface / triangulation techniques is a very high probability for any knot you can draw in a short amount of time. And that conclusion is reached by computing for plenty of examples. If you have any complicated knots I'd be happy to run Regina over it. | |
| Feb 28, 2016 at 6:31 | comment | added | mme | @RyanBudney: How good are they, usually? Better than the Bar-Natan's mentioned "usually $O(\exp(\sqrt n))$ time" algorithm? | |
| Feb 27, 2016 at 18:48 | comment | added | Ryan Budney | The unknotting problem was solved a long time ago, it sounds like you are interested in polynomial-time unknot recognition. The exponential-time algorithms using normal surface theory have "most of the time" better than exponential run-times. To me it seems like this route is still the most enticing way to make progress on your problem. | |
| Feb 27, 2016 at 16:31 | comment | added | Mariano Suárez-Álvarez | $O(\sqrt{\text{crossings}})$ does not give time enough to even look at all the crossings. | |
| Feb 27, 2016 at 15:10 | comment | added | Christopher King | Don't forget infinite knots. | |
| Feb 27, 2016 at 13:02 | answer | added | Dylan Thurston | timeline score: 41 | |
| Feb 27, 2016 at 11:33 | vote | accept | Omri | ||
| Feb 27, 2016 at 11:23 | comment | added | Sam Nead | Omri - Thanks for this. I've posted a short answer below. | |
| Feb 27, 2016 at 11:22 | answer | added | Sam Nead | timeline score: 39 | |
| Feb 27, 2016 at 11:07 | comment | added | Omri | Hi Sam, here: arxiv.org/abs/math/0606318 | |
| Feb 27, 2016 at 10:49 | comment | added | Sam Nead | "Bar-Natan showed a program to compute the Khovanov homology fast:" What is the reference for this, please? | |
| Feb 27, 2016 at 9:09 | review | First posts | |||
| Feb 27, 2016 at 9:24 | |||||
| Feb 27, 2016 at 9:02 | history | asked | Omri | CC BY-SA 3.0 |