Mathematical Conversations

Many problems in classical topology can be formulated as decision problems, with yes/no answer and an algorithm as a solution. While such problems often appear to be intuitively hard, we still know little about lower bounds on their algorithmic complexity. For example, distinguishing knots started as a knot tabulation effort in Victorian England, and is still ongoing. A number of intricate algorithms now exist. While this makes the problem decidable, none of the algorithms are polynomial, and there are no known lower bounds on the complexity of this problem. We will review recent advances concerning complexity of related problems: recognizing an unknot, detecting various sublinks, getting from one link diagram to another by Reidemesiter moves, and homeomorphism of 3-manifolds. Aside from long term interest of topologists in these problems, they provide new examples of problems that are NP-hard, NP-complete, or lie in the intersection of NP and co-NP classes, but do not have a known polynomial algorithm.