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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456