Low-dimensional topology and geometry have many problems with an easy formulation, but a hard solution. Despite our intuitive feeling that these problems are "hard", lower or upper bounds on algorithmic complexity are known only for some of them. Recently, several problems that lie at the heart of classical knot theory were shown to be NP-hard. We will discuss the problems related to unlinking and splitting by crossing changes, to Reidemeister moves, and to detecting sublinks with various properties. Based on joint work with Dale Koenig.