Timeline for Are there knot theoretic formulations of NP complete problems?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 12, 2014 at 8:04 | comment | added | Noam Zeilberger | no, you're right, I was just being dense. Fixed now. | |
| Nov 12, 2014 at 8:04 | history | edited | Noam Zeilberger | CC BY-SA 3.0 |
in NP, not NP-hard
|
| Nov 11, 2014 at 19:57 | comment | added | Abel Molina | Maybe being dense here, but not clear why the results are characterized in the answer as talking about knottedness/unknottedness "being NP-hard", rather than "being in NP", since as far as I can see in the abstract, they assert that the problems are in NP, but not that they are NP-Complete as well. | |
| Nov 6, 2014 at 12:45 | comment | added | Noam Zeilberger | thanks for your precision: I've included it into the text. | |
| Nov 6, 2014 at 12:45 | history | edited | Noam Zeilberger | CC BY-SA 3.0 |
added Arnaud's precision
|
| Nov 6, 2014 at 12:38 | comment | added | Arnaud | And a small precision: the Agol, Hass, Thurston NP-hardness proof only applies in general 3-manifolds, and not for knot genus in $\mathbb{R}^3$. Very few hardness results are known for topological problems in $\mathbb{R}^3$ and $\mathbb{S}^3$. | |
| Nov 6, 2014 at 12:34 | comment | added | Arnaud | The never published co-NP proof of Agol using sutured hierarchies is briefly summarized in a recent survey of Lackenby: people.maths.ox.ac.uk/lackenby/ekt11214.pdf | |
| Nov 6, 2014 at 12:26 | history | answered | Noam Zeilberger | CC BY-SA 3.0 |