Logic-Topology Seminar: Complexity in knot theory

Time: Monday, October 3, 4:45-6:00 pm

Place: Rome Hall 350

Speaker: Jozef Przytycki, GWU

Title: Complexity in knot theory

Abstract: Alan Turing (1912–1954), in a popular article published in the year he died, stated several “Solvable and unsolvable problems” in mathematics. In particular, he considers elementary moves on knots placed on the unit lattice in R^3. He concludes: “A similar decision problem which might well be unsolvable is the one concerning knots.”
From Turing’s times, complexity problems in knot theory have been an important part of research. Turing probably knew about the result of Markov (published only in 1958) on the unsolvability of the homeomorphy problem for 4-dimensional manifolds. In 1962, Haken proved that the knot recognition problem is solvable (his method, with some gaps, worked for arbitrary compact 3-manifolds). Recently, in February 2021, Marc Lackenby, a student of W.B.R. Lickorish, presented a new unknot recognition algorithm that runs in quasi-polynomial time.
In 1961, H. Schubert, using Haken’s method, showed that the problem of finding the genus of a knot is solvable. William Thurston (1946–2012) with Ian Agol and Joel Hass showed that finding the genus of a knot in an arbitrary 3-manifold is NP-complete (the problem in classical knot theory is still open).
I will also discuss some other complexity problems in knot theory finishing with my work with
Marithania Silvero on our conjecture that finding Khovanov homology for links with fixed braid index has polynomial time complexity.
No prior knowledge of knot theory is needed.