Session A4 - Computational Geometry and Topology
July 11, 18:30 ~ 18:55 - Room B7
The complexity of unknot recognition
University of Oxford, United Kingdom - email@example.com
The problem of deciding whether a given knot diagram represents the unknot is known to be solvable, but its complexity class is not fully understood. It is known to be in NP and co-NP, but it is not known whether there is a polynomial-time algorithm. I will briefly discuss some of the existing algorithms and will explain why there is little hope that they can be made to run in anything faster than exponential time. I'll then describe a new unknot recognition algorithm. I conjecture that there is a version of this algorithm that runs in quasi-polynomial time.