[Topology and Geometry Seminar] "Computationally hard problems in knot theory" by Dale Koenig

A decision problem is said to be NP-hard if it is provably as difficult as the hardest problems in NP.  Such problems are thought of as provably difficult for computers to solve.  It turns out many natural problems about knots or links are NP-complete or NP-hard.  I will give an introduction to computational complexity and describe a couple NP-complete problems.  I will then provide two proofs that the SUBLINK problem is NP-hard, the first given Marc Lackenby in 2016.