Pure Maths Colloquium: The complexity of knots
13 October 2014 16:00 in CM221
It was Alan Turing who first asked whether there is an algorithm to decide whether two knots are equivalent. It is now known that there is such an algorithm. But the complexity of this problem is far from well understood. In my talk, I will give a survey of the current state of our knowledge. For example, I will explain why the problem of deciding whether a given knot is trivial is in NP and co-NP. My aim is to make this talk accessible to non-specialists, and so no prior knowledge of complexity theory or knot theory will be assumed.
Contact email@example.com for more information