  We show that three natural decision problems about links and 3-manifolds are
computationally hard, assuming some conjectures in complexity theory. The first
problem is determining whether a link in the 3-sphere bounds a Seifert surface
with Thurston norm at most a given integer; this is shown to be NP-complete.
The second problem is the homeomorphism problem for closed 3-manifolds; this is
shown to be at least as hard as the graph isomorphism problem. The third
problem is determining whether a given link in the 3-sphere is a sublink of
another given link; this is shown to be NP-hard.
