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 wether a link contains a trivial sublink with n components, computing the unlinking number of a link, and computing a variety of invariants related to four-dimenional topology (such as the 4–ball Euler characteristic, the slicing number, and the 4–dimensional clasp number). This is joint work with Arnaud de Mesmay, Eric Sedgwick and Martin Tancer.