Hacker News Reader

Comment by j2kun | Hacker News Reader

Submitting in the comment box on the blog failed with "Could not open socket," so I'll post my question here.

Now that you have a notation (even if it may not be complete, you've raised the question in exercise 5), I am curious about computation.

1. Given two knots that are describable in this notation, is there an algorithm that decides if they are equivalent?

2. If so, what is the known (time/space) complexity of this problem?

View on HN

From a browse on wikipedia it looks like knot equivalence is decidable. If I'm reading [1] correctly however, it looks like strong bounds on the complexity of knot equivalence in general haven't been found.

[1] http://arxiv.org/abs/math/9712269

Good questions! But remember this is a theory that I am developing along as we go with a bunch of kids. We may end up with a lot of open problems.

For (1) I think the answer is 'yes' because the knots are finite structures. For (2) I don't know.

The reason I don't think it's so obvious is because, while the input knots may be finite structures, the transformation between the two might be unbounded in size. E.g., one can repeatedly "blow up" a knot presentation by adding in superfluous expansions of identities like L=LL; it might be the case that certain combinations of these trivial identities combine to make some nontrivial manipulations of a knot.

This is essentially the reason why there is no algorithm, which when given a finite group presentation and two input words, can decide whether the two words represent the same group element.

Reply on news.ycombinator.com