Link crossing number is NP-hard
Arnaud de Mesmay (LIGM, Université Paris Est)
03-Nov-2020, 17:30-18:00 (3 years ago)
Abstract: Most invariants in knot theory are very hard to compute in practice, yet only few computational hardness proofs are known. In this talk, we survey the computational complexity of many problems coming from knot theory, emphasizing the numerous open problems, and we present a proof of NP-hardness for the crossing number of a link.
Joint work with Marcus Schaefer and Eric Sedgwick.
computational complexitydiscrete mathematicscombinatoricsgeneral topology
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
Organizers: | Igor Pak*, Greta Panova |
*contact for this listing |
Export talk to