The complexity of knots
Mathematics Colloquium
In his final paper in 1954, Alan Turing wrote No systematic method is yet known by which one can tell whether two knots are the same.' Within the next 20 years, Wolfgang Haken and Geoffrey Hemion had discovered such a method. However, the computational complexity of this problem remains unknown. In my talk, I will give a survey on this area, that draws on the work of many low-dimensional topologists and geometers. Unfortunately, the current upper bounds on the computational complexity of the knot equivalence problem remain quite poor. However, there are some recent results indicating that, perhaps, knots are more tractable than they first seem. Specifically, I will explain a theorem that provides, for each knot type K, a polynomial p_K with the property that any two diagrams of K with n_1 and n_2 crossings differ by at most p_K(n_1) + p_K(n_2) Reidemeister moves.