News for hackers. Stuff that matters.
Re:Inventing an algebraic knot theory for eight year olds (III) by j2kun on Monday May 11, 2015 @10:08AM (#9524817)
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?

Re:Inventing an algebraic knot theory for eight year olds (III) by 14113 on Tuesday May 12, 2015 @06:30AM (#9530663)
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

Re:Inventing an algebraic knot theory for eight year olds (III) by danghica on Monday May 11, 2015 @11:11AM (#9525325)
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.

Re:Inventing an algebraic knot theory for eight year olds (III) by j2kun on Monday May 11, 2015 @02:59PM (#9527053)
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.