Re:Neural Networks, Manifolds, and Topology
by ejenk on Wednesday April 09, 2014 @10:40AM
(#7559539)
I think the author has confused NP with NP-hard (or NP-complete). Indeed, it is extremely unlikely that the unknottedness problem is NP-complete, as it is already in NP ∩ co-NP (assuming the generalized Riemann hypothesis). Furthermore, we know that the problem of computing many knot invariants is "only" BQP-complete, so it's possible that unknottedness is in BQP (i.e., efficiently solvable by quantum computers), though I don't know the expert opinion on this.
[ Parent
| on HN ]
Indeed I read that as NP-complete. That's very interesting, do you have any references on it?
Even if knots are ruled out, there might be hard topological decision problems that can be reduced to linear separability under homeomorphism, maybe in higher dimension.