Conference abstracts

Session A4 - Computational Geometry and Topology

July 11, 18:30 ~ 18:55 - Room B7

The complexity of unknot recognition

Marc Lackenby

University of Oxford, United Kingdom   -

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.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.