Martin Tancer: Hardness of invariants of knots and links and of embeddability in the 3-space
Time: Wed 2019-05-29 10.00 - 10.50
Lecturer: Martin Tancer, Charles University in Prague
Location: Room 3418, Lindstedtsvägen 25. Department of Mathematics, KTH
Abstract: The unknot recognition problem asks whether a given diagram of a knot is actually an unknot, that is, whether it can be untangled by a finite number of Reidemeister moves to a diagram without crossings. According to the current state of art, this problem belongs to computational complexity classes NP and co-NP. This is an indication for the hope that this problem could turn out to be solvable in polynomial time.
We show that a minor modification of this problem already yields NP-hardness. Namely if we want to determine whether a given diagram of a knot can be untangled with at most k Reidemeister moves (where k is a part of the input), then the problem becomes NP-hard, therefore it is not believed to be polynomial time solvable. This shows limitations how may an efficient algorithm for the unknot recognition problem behave.
Our proof is based on a suitable "gadget" built on the properties of the Borromean rings and the Hopf link. It turns out that similar constructions yield NP-hardness of several other problems including trivial sublink problem, computation of several 4-dimensional knot invariants, but also a bit surprisingly recognition of embeddable complexes in R^3.
The talk is based on two joint works with A. de Mesmay, Y. Rieck and E. Sedgwick