  In this paper we prove that the problem of deciding contractibility of an
arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize
that the manifold and the curve are both inputs to the problem. Moreover, our
algorithm also works if the curve is given as a compressed word. Previously,
such an algorithm was known for simple (non-compressed) curves, and, in very
limited cases, for curves with self-intersections. Furthermore, our algorithm
is fixed-parameter tractable in the complexity of the input 3-manifold.
  As part of our proof, we obtain new polynomial-time algorithms for compressed
curves on surfaces, which we believe are of independent interest. We provide a
polynomial-time algorithm which, given an orientable surface and a compressed
loop on the surface, computes a canonical form for the loop as a compressed
word. In particular, contractibility of compressed curves on surfaces can be
decided in polynomial time; prior published work considered only constant genus
surfaces. More generally, we solve the following normal subgroup membership
problem in polynomial time: given an arbitrary orientable surface, a compressed
closed curve $\gamma$, and a collection of disjoint normal curves $\Delta$,
there is a polynomial-time algorithm to decide if $\gamma$ lies in the normal
subgroup generated by components of $\Delta$ in the fundamental group of the
surface after attaching the curves to a basepoint.
