  We prove 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. We
also prove that several natural questions regarding links in the $3$-sphere are
NP-hard, including detecting whether a link contains a trivial sublink with $n$
components, computing the unlinking number of a link, and computing a variety
of link invariants related to four-dimensional topology (such as the $4$-ball
Euler characteristic, the slicing number, and the $4$-dimensional clasp
number).
