Combinatorics Seminar

16:00-18:00

Speaker: Martin Tancer

Title: The unbearable hardness of unknotting

Abstract: During the talk, I will sketch a proof that deciding if a diagram of the unknot can be untangled using at most k Riedemeister moves (where k is part of the input) is NP-hard. (This is not the same as the unknot recognition but it reveals some difficulties.) Similar ideas can be also used for proving that several other similar invariants are NP-hard to recognize on links.

Joint work with A. de Mesmay, Y. Rieck and E. Sedgwick.